思考

本身题目较为简单，但是其中引出一个问题，平时用的二分查找本身的目的是在一个有序数组中找到某一个数，但在这道题的题解中如何通过二分法找到重复数字的左右边界。

二分法找到重复数字的右边界

function binarySearch(nums: Array<number>, target:number):number {
    let left = 0, right = nums.length - 1, mid = 0
    while(left < right) {
        mid = right - divide(right - left, 2)
        if(nums[mid] <= target) {
            left = mid
        }else {
            right = mid - 1
        }
    }
    return left;
}

二分法找到重复数字的左边界

function binarySearch(nums: Array<number>, target:number):number {
    let left = 0, right = nums.length - 1, mid = 0
    while(left < right) {
        mid = left + divide(right - left, 2)
        if(nums[mid] < target) {
            left = mid + 1
        }else {
            right = mid
        }
    }
    return left;
}

注意点

1. divide方法为Math.floor(a/b)
2. 左边界与右边界中计算mid的不同是为了保证每次left,right都在向中间移动避免死循环的问题出现，举例对于nums:[0,1,1], target: 1而言,第二轮left = 0,right = 1如果使用right - divide(right - left, 2)则会导致无限循环，反之采取left + divide(right - left , 2)则最终会得到左边界，右边界亦然。