34. 在排序数组中查找元素的第一个和最后一个位置

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) {
 4 
 5         vector<int> ret;
 6         int n = nums.size();
 7         int first = -1;
 8         int l = 0;
 9         int r = n-1;
10         while(l<=r)//如果用一个过程，同时找两个边界，当遇到等于目标时左右扫描找边界
11         {          //这种算法当数组全等于目标时就退化成线性算法而不是o(logn)算法了
12             int mid = l+(r-l)/2;
13             if(nums[mid] == target)
14             {
15                 first = mid;//在查找过程中使用一个变量随时跟踪记录信息
16                 if(mid>l && nums[mid-1] == target)//如果还有左边，并且左边等于目标
17                     r=mid-1;
18                 else//其他情况或者没有左边或者左边的值不等于目标
19                     break;
20             }
21             else if(nums[mid]>target)
22                 r=mid-1;
23             else
24                 l=mid+1;
25 
26         }
27         
28         int second = -1;
29         l = 0;
30         r = n-1;
31         while(l<=r)
32         {
33             int mid = l+(r-l)/2;
34             if(nums[mid] == target)
35             {
36                 second = mid;
37                 if(mid<r && nums[mid+1] == target)//如果还有右边，并且右边等于目标
38                     l=mid+1;
39                 else//其他情况或者没有右边或者右边的值不等于目标
40                     break;
41             }
42             else if(nums[mid]>target)
43                 r=mid-1;
44             else
45                 l=mid+1;
46 
47         }
48 
49         ret.push_back(first);
50         ret.push_back(second);
51 
52         return ret;
53         
54     }
55 
56 };