一刷283-二分模块-剑指 Offer 53 - I. 在排序数组中查找数字 I（e）

题目：
统计一个数字在排序数组中出现的次数。
---------------
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
 
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
----------------
思路：
排序数组中的搜索问题，首先想到 二分法 解决
排序数组 nums 中的所有数字 target形成一个窗口，
记窗口的 左 / 右边界 索引分别为 left和 right ，分别对应窗口左边 / 右边的首个元素。

本题要求统计数字 target的出现次数，可转化为：
使用二分法分别找到 左边界 left和 右边界 right，
易得数字 target的数量为 right - left - 1
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

算法解析：
初始化： 左边界 i = 0，右边界 j = len(nums) - 1
循环二分： 当闭区间 [i, j]无元素时跳出；
计算中点 m = (i + j) / 2（向下取整）；
1、若 nums[m] < target，则 target闭区间 [m + 1, j] 中，因此执行 i = m + 1
2、若 nums[m] > target，则 target在闭区间 [i, m - 1]中，因此执行 j = m - 1

3、若 nums[m] = target，则右边界 right在闭区间 [m+1, j]中；左边界 left在闭区间 [i, m-1]中。
因此分为以下两种情况：
	1、若查找 右边界 right，则执行 i = m + 1；（跳出时 i 指向右边界）
	2、若查找 左边界 left，则执行 j = m - 1；（跳出时 j 指向左边界）
返回值： 应用两次二分，分别查找 right 和 left，最终返回 right - left - 1即可。
--------------------------------
效率优化：
以下优化基于：查找完右边界 right = i 后，则 nums[j]指向最右边的 target（若存在）。
查找完右边界后，可用 nums[j] = j判断数组中是否包含 target，
若不包含则直接提前返回 0 ，无需后续查找左边界。
查找完右边界后，左边界 left一定在闭区间 [0, j]中，
因此直接从此区间开始二分查找即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如上图所示，由于数组 nums中元素都为整数，
因此可以分别二分查找 target 和 target - 1的右边界，将两结果相减并返回即可。
-------------------
class Solution {//分别二分查找 target 和 target - 1的右边界，将两结果相减并返回即可。
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    private int helper(int[] nums, int target) {
        int left = 0;//左右指针
        int right = nums.length - 1;
        while (left <= right) {//二分查找：循环条件
            int mid = left + ((right - left) >> 1);//二分中点mid
            if (nums[mid] <= target) {// 分两种情况 
                left = mid + 1; 
            }else right = mid - 1;
        }
        return right;//返回值为target目标值的右边界
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LC