原題連結
題意:給你一個目标值,或者傳回其在數組中的下标位置,或者傳回-1(表示不存在,查找失敗)。
例如 0 1 2 4 5 6 7 可能成為 4 5 6 7 0 1 2.
思路分析:
用二分搜尋來找到轉折點,也就是最小數的位置。對二分搜尋要稍作修改,當a[left]<=a[mid],可以肯定a[left...mid]是升序的,那麼a[left]是最小的,也可能最小的在a[mid+1...right]中,是以要比較a[left]和min{a[mid+1...right]},同樣對于a[left]>a[mid],做相應的處理。
來看代碼:
1 class Solution {
2 public:
3 int findPos(vector<int>& nums,int left,int right){
4 //if (nums.empty())//多餘
5 // return -1;
6 if (left > right||left>=nums.size())//後面這個條件不要,一些測試用例會産生下标越界錯誤
7 return -1;
8 int mid = (left + right) / 2;
9 if (nums[left] <= nums[mid])
10 {
11 int pos = findPos(nums, mid + 1, right);
12 if (pos == -1)
13 return left;
14 else
15 return nums[left] < nums[pos] ? left : pos;
16 }
17 else
18 {
19 int pos = findPos(nums, left, mid - 1);
20 if (pos == -1)
21 return mid;
22 else
23 return nums[mid] < nums[pos] ? mid :pos;
24 }
25 }
26 int bsearch(vector<int>nums, int left, int right, int key)
27 {
28 if (left>right)
29 return -1;
30 int mid = (left + right) / 2;
31 if (nums[mid] == key)
32 return mid;
33 if (nums[mid] < key)
34 return bsearch(nums, mid + 1, right, key);
35 else
36 return bsearch(nums, left, mid - 1, key);
37 }
38 int search(vector<int>& nums, int target)
39 {
40 int len = nums.size();
41 int pos = findPos(nums, 0, len);
42 int index;
43 if ((index=bsearch(nums, 0, pos - 1,target)) != -1)
44 return index;
45 else return bsearch(nums, pos, len, target);
46
47 }
48 };
轉載于:https://www.cnblogs.com/chess/p/5185526.html