算法笔记 -- 二分查找

2021-10-31 19:56:58 1.9k 字 · 约 8 分钟 # algorithm # algorithm # 计算机基础

$d e f in e$

二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。

在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作，这就是所谓的查找空间。

二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；

如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。

如果查以空的一半结束，则无法满足条件，并且无法找到目标。

标准二分查找

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

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // End Condition: left > right
    return -1;
}

上述模板是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板，用于查找可以通过访问数组中的单个索引来确定的元素或条件。

为什么 $w hi l e$ 循环的条件中是 $<=$ ，而不是 $<$ ？

因为初始化 $r i g h t$ 的赋值是 $n u m s . l e n g t h - 1$ ，即最后一个元素的索引，而不是 $n u m s . l e n g t h$ 。因此搜索区间为 $[l e f t, r i g h t]$ 的闭区间。循环结束的条件为 $l e f t > r i g h t$ ，即区间为空，也就不存在元素了。

再看leetcode上的一道使用标准二分的题：

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int low = 1, high = x;
        while (low <= high) {
            int mid = low + (high - low) >> 1;
            if (x / mid == mid) {
                return mid;
            } else if (x / mid > mid) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high;
    }
}

题目要返回的是一个确定的值，所以考虑使用标准二分查找。

考虑这样的原理：如果一个数 $a$ 的平方大于 $x$ ，那么 $a$ 一定不是 $x$ 的平方根，下一轮就需要在区间 $[0... a - 1]$ 内查找；

所以高位 $hi g h$ 就一定会停在 $mi d \times mi d \leq x$ 的最大的那个 $mi d$ 位置，因为上述若存在 $mi d \times mi d = x$ 的话就直接返回了。

在考虑这样的一个题目：

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1, high = n, mid = -1;
        while(low <= high) {
            mid = low + ((high - low) >> 1);
            if (guess(mid) == 1) {
                low = mid + 1;
            } else if (guess(mid) == -1) {
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return mid;
    }
}

题目要返回的也是一个确定的值，且有 $a p i$ 方法 $g u ess (n u m)$ 告诉我们当前数字是大了还是小了。

所以直接套标准二分查找模板即可，如果 $g u ess ()$ 返回值为1，那么说明当前的 $mi d$ 比 $p i c k$ 小了，移动 $l o w$ ，

同理若返回值为-1，移动 $hi g h$ 。

再来看一道二分查找的变种：

判断 $mi d$ 所在元素是左递增还是右递增。

若 $n u m s [mi d] \geq n u m s [l o w]$ ，说明从 $[l o w ... mi d]$ 是往右递增，再判断 $t a r g e t$ 是否落在此区间中；

若 $n u m s [mi d] < n u m s [l o w]$ ，说明 $n u m s [mi d]$ 落在第二部分的有序数组中，再判断 $t a r g e t$ 的位置；

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid = -1;
        while(low <= high) {
            mid = low + ((high - low) >> 1);
            if(nums[mid] == target) {
                return mid;
            } else if (nums[low] <= nums[mid]){
                if(target < nums[mid] && target >= nums[low]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if(target <= nums[low] && target > nums[mid]) {
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
}

寻找左侧边界的二分查找

int leftBound(int[] nums.int target) {
    if (null == nums || nums.length == 0) {
        return -1;
    }
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return return nums[left] == target ? left : -1;
}

为什么 $w hi l e (l e f t < r i g h t)$ 而不是 $<=$ ?

因为初始化 $r i g h t = n u m s . l e n g t h$ 而不是 $n u m s . l e n g t h - 1$ 。因此每次循环的「搜索区间」 $[l e f t, r i g h t)$ 是一个左闭右开的区间。 $l e f t <= r i g h t$ 的终止条件是 $l e f t > r i g h t$ ，这时候区间为空，不存在要找的边界。而 $l e f t < r i g h t$ 的终止条件是 $l e f t == r i g h t$ ，此时区间不为空，才存在要找的边界索引。

为什么 $l e f t = mi d + 1$ ， $r i g h t = mi d$ ？

因为我们的「搜索区间」是 $[l e f t, r i g h t)$ 左闭右开，所以当 $n u m s [mi d]$ 被检测之后，下一步的搜索区间应该去掉 $mi d$ 分割成两个区间，即 $[l e f t, mi d)$ 或 $[mi d + 1, r i g h t)$ 。

为什么该算法能够搜索左侧边界？

关键在于对于 $n u m s [mi d] == t a r g e t$ 这种情况的处理。找到 $t a r g e t$ 时不要立即返回，而是缩小「搜索区间」的上界 $r i g h t$ ，在区间 $[l e f t, mi d)$ 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

寻找右侧边界的二分查找

int rightBound(int[] nums, int target) {
    if (nums.length == 0) {
        return -1;
    }
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; 
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return nums[right - 1] == target ? right - 1 : -1; 
}

为什么这个算法能够找到右侧边界?

当 $n u m s [mi d] == t a r g e t$ 时，不要立即返回，而是增大「搜索区间」的下界 $l e f t$ ，使得区间不断向右收缩，达到锁定右侧边界的目的。

为什么要减1?

因为我们对 $l e f t$ 的更新必须是 $l e f t = mi d + 1$ ，就是说 $w hi l e$ 循环结束时， $n u m s [l e f t]$ 一定不等于 $t a r g e t$ 了，而 $n u m s [l e f t - 1]$ 可能是 $t a r g e t$ 。

对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的「搜索区间」，我们还根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

2021-10-31 19:56:58 # algorithm # algorithm # 计算机基础

define

标准二分查找

寻找左侧边界的二分查找

寻找右侧边界的二分查找

$d e f in e$