LeetCode
tip 二进制右移一位
将一个二进制数右移一位就等于将这个数除以2,这与十进制中将一个数除以10相似。例如二进制数 1000 (十进制的 8) 右移一位变为 100(十进制的 4),就相当于做了除以2的操作。因此,假设有两个数 a 和 b,(a + b) >>> 1 的操作其实相当于 (a + b) / 2,也就是求两个数的平均值。
如果 a 和 b 都是非常大的整数,即它们的和超过了 JavaScript 的数值精度极限(Number.MAX_SAFE_INTEGER),则 (a + b) 可能会发生溢出。
INFO
位运算可以避免由于大数相加造成的溢出问题
题解
[left, right] 左比右闭
typescript
function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
// 求出 mid 的索引(向下取整)
let mid = (left + right) >>> 1;
// 1. 相等,直接返回mid
if(nums[mid] === target) return mid
// 2. 中间数比target小,缩小左区间
if(nums[mid] < target ){
left = mid + 1
} else {
// 3. 中间数比target大,target在左边,缩小右区间边界
right = mid - 1
}
}
return -1;
};
[left, right) 左闭右开
typescript
function search(nums: number[], target: number): number {
let left = 0;
// 1. 右边取不到,不用减1了
let right = nums.length;
// 2. 比较的时候,也取不到右边,等号不要
while (left < right) {
let mid = (left + right) >>> 1;
// 1. 相等,直接返回mid
if(nums[mid] === target) return mid
// 2. 中间数比target小,缩小左区间
if(nums[mid] < target ){
left = mid + 1
} else {
// 3. 中间数比target大,target在左边,缩小右区间边界
right = mid
}
}
return -1;
};