二分查找 | 暗暗那的个人博客

代码随想录

https://programmercarl.com/0704.二分查找.html#算法公开课

题目

704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

笔记

什么是二分法？
在一个有序序列中找一个目标数target，先把数组一分为二，看target比数组的中点数大还是小，来判断target在数组的右半边还是左半边。假如在左半边，就再把左半边一分为二来找，直到找到target或找完整个数组。每次框定区间时，left指向数组在区间中国呢的最左边索引，right指向最右边索引，middle指向中点索引，若中点索引不是整数，则middle取小于且最接近中点索引的整数。

实际编写二分法的三个易错点：

一开始right应该取arr.length还是arr.length - 1？
循环继续的条件是left < right还是left <= right
循环中移动right时，是移到middle，还是middle - 1？移动left呢？

这几个问题取决于我们在搜索过程中对于取值区间的定义，是左闭右开[left,right)，还是左闭右闭[left,right]。

若对区间的定义是左闭右闭，则：

一开始取的left和right要满足[left, right]能包含数组中的所有值，所以可以取left=0，right=arr.length - 1
当left===right时，[left,right]也是合法的区间，也是需要被查找的，所以要等到left < tight才能确定数组里找不到target。
当arr[mid] > targer时，就确定了mid位置没有target，而[left,mid]包括mid，所以right应该移到mid - 1处。
当arr[mid] < targer时，[mid,right]包括mid，所以right应该移到mid - 1处。

若对区间的定义是左闭右开，则：

一开始取的left和right要满足[left, right)能包含数组中的所有值，所以可以取left=0，right=arr.length
当left===right时，[left,right)不是合法的区间，所以除了left < tight能确定找不到，left = tight也能。
当arr[mid] > targer时，就确定了mid位置没有target，而[left,mid)不包括mid，所以right移到mid处就行。
当arr[mid] < targer时，[mid,right)包括mid，所以right应该移到mid - 1处。这一点和左闭右闭是一样的。

左闭右闭版

我个人比较喜欢左闭右闭，不用考虑哪里是开区间哪里是闭区间。

const search = (arr, target) => {
    let l = 0, r = arr.length - 1, mid;
    while (l <= r) {
        mid = l + ((r - l) >> 1);
        if (target < arr[mid]) {
            r = mid - 1;
        } else if (target > arr[mid]) {
            l = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

左闭右开版

若一开始r取了arr.length - 1，就会在search([3], 3)时翻车。

const search = (arr, target) => {
    let l = 0, r = arr.length, mid;// 区别1
    while (l < r) { // 区别2
        mid = l + ((r - l) >> 1);
        if (target < arr[mid]) {
            r = mid; // 区别3
        } else if (target > arr[mid]) {
            l = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

自我摸索版

在只知道基本原理，还没看讲解时，我自己在力扣写了一遍。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    const func = () => {
        if (left > right) {
            return -1;
        }
        const mid = left + Math.floor((right - left) / 2);
        if (target > nums[mid]) {
            left = mid + 1;
            return func();
        } else if (target < nums[mid]) {
            right = mid - 1;
            return func();
        } else {
            return mid;
        }
    }
    return func();
};

遇到的问题有：

没想到用while就行，为了做到循环还写出来了一个递归函数
没想过我定义的区间是左闭右闭还是左闭右开，导致一边写left > right时才停止，一边写right会移到mid。
查了一下怎么向下取整，查到可以用Math.floor()
取a和b的平均值(a < b)时，可以用(b + a)/2，我当时只能的a + (b - a)/2。但是之后看了代码随想录的解答，人家也是用的小数加上二者的差，因为这样能预防两数相加时大数溢出。
我想实现a/2并忽略小数部份，写的是Math.floor(a/2)，而代码随想录用的是a >> 1。在JavaScript里，>>1 是位运算符中的右移一位操作‌。如果对一个整数 x 使用 x >> 1，则相当于将 x 除以2并向下取整（对于正数和0）或向上取整后取相反数（对于负数）。