【二分查找】面试题 10.03. 搜索旋转数组

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) 
 4     {
 5         int l = 0;
 6         int r = nums.size() -1;
 7         
 8         while (l <= r)
 9         {
10             // 补丁1：里面有重复元素
11             while (l != r && nums[l] == nums[r])
12             {
13                 r--;
14             }
15             int mid = (l + r) >> 1;
16 
17             if (target == nums[mid]) 
18             {
19                 // 补丁2 :若有多个相同元素，返回索引值最小的一个。
20                 while (mid > 0)
21                 {
22                     if (nums[mid - 1] != nums[mid])
23                     {
24                         break;
25                     }
26                     mid--;
27                 }
28                 return mid;
29             }
30 
31             if (nums[l] <= nums[mid])
32             {
33                 if (nums[l] <= target && target < nums[mid])
34                     r = mid-1;
35                 else
36                     l = mid+1;
37             }
38             else
39             {
40                 if (nums[mid] < target && target <= nums[r])
41                     l = mid +1;
42                 else
43                     r = mid -1;
44             }
45         }
46         return -1;
47 
48     }
49 };