classSolution { public: intsearch(vector<int>& nums, int target){ int n = nums.size(), idx = -1; for (int i = 0; i < n - 1 && idx == -1; i++) { if (nums[i] > nums[i + 1]) idx = i; } int ans = find(nums, 0, idx, target); if (ans != -1) return ans; return idx + 1 < n ? find(nums, idx + 1, n - 1, target) : ans; } intfind(vector<int>& nums, int l, int r, int target){ while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } return nums[l] == target ? l : -1; } };
Python 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution: defsearch(self, nums: List[int], target: int) -> int: n, idx = len(nums), -1 for i inrange(0, n - 1): if nums[i] > nums[i + 1]: idx = i break
deffind(L, R): l, r = L, R while l < r: mid = l + r >> 1 if nums[mid] >= target: r = mid else: l = mid + 1 return l if nums[l] == target else -1
ans = find(0, idx) if ans != -1: return ans return find(idx + 1, n - 1) if idx + 1 < n else ans
TypeScript 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
functionsearch(nums: number[], target: number): number { let n = nums.length, idx = -1; for (let i = 0; i < n - 1 && idx == -1; i++) { if (nums[i] > nums[i + 1]) idx = i; } const find = function(l: number, r: number): number { while (l < r) { let mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } return nums[l] == target ? l : -1; } let ans = find(0, idx); if (ans!= -1) return ans; return idx + 1 < n ? find(idx + 1, n - 1) : ans; };
classSolution { publicintsearch(int[] nums, int target) { intn= nums.length;
// 第一次「二分」:从中间开始找,找到满足 >=nums[0] 的分割点(旋转点) intl=0, r = n - 1; while (l < r) { intmid= l + r + 1 >> 1; if (nums[mid] >= nums[0]) l = mid; else r = mid - 1; }
// 第二次「二分」:通过和 nums[0] 进行比较,得知 target 是在旋转点的左边还是右边 if (target >= nums[0]) { l = 0; } else { l = l + 1; r = n - 1; } while (l < r) { intmid= l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; }
classSolution { public: intsearch(vector<int>& nums, int target){ int n = nums.size();
// 第一次「二分」:从中间开始找,找到满足 >=nums[0] 的分割点(旋转点) int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] >= nums[0]) l = mid; else r = mid - 1; }
// 第二次「二分」:通过和 nums[0] 进行比较,得知 target 是在旋转点的左边还是右边 if (target >= nums[0]) { l = 0; } else { l = l + 1; r = n - 1; } while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; }
# 第一次「二分」:从中间开始找,找到满足 >=nums[0] 的分割点(旋转点) l, r = 0, n - 1 while l < r: mid = l + r + 1 >> 1 if nums[mid] >= nums[0]: l = mid else: r = mid - 1
# 第二次「二分」:通过和 nums[0] 进行比较,得知 target 是在旋转点的左边还是右边 if target >= nums[0]: l = 0 else: l, r = l + 1, n - 1 while l < r: mid = l + r >> 1 if nums[mid] >= target: r = mid else: l = mid + 1
functionsearch(nums: number[], target: number): number { const n = nums.length;
// 第一次「二分」:从中间开始找,找到满足 >=nums[0] 的分割点(旋转点) let l = 0, r = n - 1; while (l < r) { let mid = l + r + 1 >> 1; if (nums[mid] >= nums[0]) l = mid; else r = mid - 1; }
// 第二次「二分」:通过和 nums[0] 进行比较,得知 target 是在旋转点的左边还是右边 if (target >= nums[0]) { l = 0; } else { l = l + 1; r = n - 1; } while (l < r) { let mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; }