Skip to content

LeetCode

704. 二分查找

image.png

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] 左比右闭

image.png

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;
};

参考

  1. 卡尔:《代码随想录》