双指针法遍历顺序数组

题目链接-来源：力扣（LeetCode）

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

思路：

我们可以很容易地想到遍历整个数组，计数 target 出现的次数，只需 O(n) 的复杂度。
但是注意到数组有序，有序必定想到二分法，降低复杂度至 O(logn)。
在数组中二分地找到任意一个与 target 相等的值是容易的，但我们需要统计次数，如果在找到某个 target 以后，最坏情况下整个数组相等且等于 target，我们又回到了 O(n) 复杂度。
也就是说，在找到 target 确定其存在以后，我们还需要二分地找到其两侧边界。这里我们可以做一个巧妙的处理，用一个辅助函数 helper() 执行二分，我们将二分缩小左边界的条件从 target > nums[m] 改为 target >= nums[m]（nums[m] 为当前二分区间中点值），这样我们二分停止处的点就是「大于 target 的第一个值」。这样一来，target 起始处之前的下标就是 helper(target - 1)，终止处的下标就是 helper(target)，二者之差就是 target 出现的次数。

时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    
    private int helper(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (target >= nums[m]) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
}