【二分查找】面试题53 - I. 在排序数组中查找数字 I

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