剑指 Offer 53 - I. 在排序数组中查找数字 I（改进二分）

二分查找找到一个target，然后往两侧开始计数

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int pos = -1;

        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] == target){
                // 找到
                pos = mid;
                break;
            }else if(nums[mid] < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        if(pos == -1){
            return 0;
        }
        int cnt = 1;
        int left = pos - 1;
        while(left >= 0 && nums[left] == target){
            cnt++;
            left--;
        }
        int right = pos + 1;
        while(right < nums.size() && nums[right] == target){
            cnt++;
            right++;
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

我们要知道，当$nums[mid]<target$时，$l$才会向右移动，也就是说，$l$不可能越过数组中任意一个$target$值。第一次$mid$指向$target$时，并不退出查找，而是继续循环，直到$l==r$才退出。

由于$l$不会越过任意一个$target$值，$r$只可能指向不大于$target$的值，我们设定的退出条件是$l==r$，如果数组中存在target，那最终退出时，$l$和$r$一定指向最左侧的$target$

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int cnt = 0;

        while(l < r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] >= target){
                // 这里mid可能指向target，不能使用r = mid - 1越过当前值
                r = mid;
            }else{
            	// 此时的mid小于target，l可以越过mid
                l = mid + 1;
            }
        }

        while(l < nums.size() && nums[l] == target){
            l++;
            cnt++;
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25