思考
本身题目较为简单，但是其中引出一个问题，平时用的二分查找本身的目的是在一个有序数组中找到某一个数，但在这道题的题解中如何通过二分法找到重复数字的左右边界。
二分法找到重复数字的右边界
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;
}
注意点
- divide方法为Math.floor(a/b)
- 左边界与右边界中计算mid的不同是为了保证每次left,right都在向中间移动避免死循环的问题出现，举例对于nums:[0,1,1], target: 1而言,第二轮left = 0,right = 1如果使用right - divide(right - left, 2)则会导致无限循环，反之采取left + divide(right - left , 2)则最终会得到左边界，右边界亦然。
