algorithm2

二分法

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

前提： 排序数组

目的： 统计出现次数

解题思路：

1. 因为是排序数组，目标值只能是连续出现，不会出现大小穿插数值; 例如：[1, 2, 2, 1, 2, 3]

2. 出现次数等于 = 结束位置 - 开始位置 + 1，即开始到结束位置的长度，找出开始位置和结束位置即可

3. 二分法找开始位置索引三种情况：a. 中间值刚好等于目标值；b.中间值大于目标值；c.中间值小于目标值

4. 中间值刚好等于目标值，意味着第一次出现目标值的位置只能小于等于当前位置，例如：[1, 2, 2, 2, 3] 找 2 的次数，当中间值刚好是 2 时，说明开始位置只能在左区间 [1, 2, 2]内，所以此时改变 right 值；但是要找结束位置的时候，则恰恰相反，改变 left 的值；

var search = function(nums, target) {
    const length = nums.length;
    let start = -1;
    let end = -1;
    let left = 0;
    let right = length - 1;
    // 找到左边界
    while (left <= right) {
        // 取二分法的中间位置
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            start = mid;
            // 我们要找左边界，那要压缩的区间就是右边的值，调整区间大小
            right = mid - 1;
        } else if (nums[mid] > target) {
            // 中间值大于目标值，说明目标值在左区间，所以缩短右区间
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    left = 0;
    right = length - 1;
    // 找到右边界：找到第2次出现
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
         // 我们要找右边界，那要压缩的区间就是左边的值，调整区间大小
        if (nums[mid] === target) {
            end = mid;
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return start <= end && start !== -1 ? end - start + 1 : 0;
};