【二分查找】34. 在排序数组中查找元素的第一个和最后一个位置（搜索范围（Search for a Range））

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) 
 4     {
 5         vector<int> range(2, -1);
 6 
 7         range[0] = left_bound(nums, target);
 8         range[1] = right_bound(nums, target);
 9         
10         return range;
11     }
12 
13     int left_bound(vector<int> nums, int target) 
14     {
15         int left = 0;
16         int right = nums.size() - 1;
17 
18         while (left <= right) 
19         {
20             int mid = left + (right - left) / 2;
21 
22             if (nums[mid] < target) 
23             {
24                 left = mid + 1;
25             } 
26             else if (nums[mid] > target) 
27             {
28                 right = mid - 1;
29             } 
30             else if (nums[mid] == target) 
31             {
32                 // 别返回，收缩左侧边界
33                 right = mid - 1;
34             }
35         }
36         
37         // 最后要检查 left 越界的情况
38         if (left >= nums.size() || nums[left] != target)
39         {
40             return -1;
41         }
42         return left;
43     }
44 
45 
46     int right_bound(vector<int> nums, int target) 
47     {
48         int left = 0;
49         int right = nums.size() - 1;
50 
51         while (left <= right) 
52         {
53             int mid = left + (right - left) / 2;
54 
55             if (nums[mid] < target) 
56             {
57                 left = mid + 1;
58             } 
59             else if (nums[mid] > target) 
60             {
61                 right = mid - 1;
62             } 
63             else if (nums[mid] == target) 
64             {
65                 // 别返回，收缩右侧边界
66                 left = mid + 1;
67             }
68         }
69         // 最后要检查 right 越界的情况
70         if (right < 0 || nums[right] != target)
71         {
72             return -1;
73         }
74         return right;
75     }
76 };