算法笔记 -- 二分查找
2021-10-31 19:56:58 # algorithm # algorithm # 计算机基础

\(define\)

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

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

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

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

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

标准二分查找

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

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

为什么 \(while\) 循环的条件中是 \(<=\)，而不是 \(<\) ？

因为初始化 \(right\) 的赋值是 \(nums.length - 1\)，即最后一个元素的索引，而不是 \(nums.length\)。因此搜索区间为\([left,right]\)的闭区间。循环结束的条件为\(left > right\)，即区间为空，也就不存在元素了。

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

image-20211031210513375 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]\)内查找；

所以高位\(high\)就一定会停在\(mid \times mid \le x\)的最大的那个\(mid\)位置，因为上述若存在\(mid \times mid = x\)的话就直接返回了。

在考虑这样的一个题目：

image-20211031211728202 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/** 
 * 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;
    }
}

题目要返回的也是一个确定的值，且有\(api\)方法\(guess(num)\)告诉我们当前数字是大了还是小了。

所以直接套标准二分查找模板即可，如果\(guess()\)返回值为1，那么说明当前的\(mid\)比\(pick\)小了，移动\(low\)，

同理若返回值为-1，移动\(high\)。

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

image-20211031214751488

判断\(mid\)所在元素是左递增还是右递增。

若\(nums[mid] \ge nums[low]\)，说明从\([low...mid]\)是往右递增，再判断\(target\)是否落在此区间中；

若\(nums[mid] \lt nums[low]\)，说明\(nums[mid]\)落在第二部分的有序数组中，再判断\(target\)的位置；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

寻找左侧边界的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

为什么 \(while(left < right)\) 而不是 \(<=\)?

因为初始化 \(right = nums.length\) 而不是 \(nums.length - 1\) 。因此每次循环的「搜索区间」 \([left, right)\)是一个左闭右开的区间。\(left <= right\)的终止条件是\(left \gt right\)，这时候区间为空，不存在要找的边界。而\(left < right\)的终止条件是 \(left == right\)，此时区间不为空，才存在要找的边界索引。

为什么 \(left = mid + 1\)，\(right = mid\) ？

因为我们的「搜索区间」是 $[left, right) $左闭右开，所以当 \(nums[mid]\) 被检测之后，下一步的搜索区间应该去掉 \(mid\) 分割成两个区间，即 \([left, mid)\) 或$ [mid + 1, right)$。

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

关键在于对于 \(nums[mid] == target\) 这种情况的处理。找到 \(target\) 时不要立即返回，而是缩小「搜索区间」的上界 \(right\)，在区间 \([left, mid)\) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

寻找右侧边界的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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; 
}

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

当 \(nums[mid] == target\) 时，不要立即返回，而是增大「搜索区间」的下界 \(left\)，使得区间不断向右收缩，达到锁定右侧边界的目的。

为什么要减1?

因为我们对 \(left\) 的更新必须是 \(left = mid + 1\)，就是说 \(while\) 循环结束时，\(nums[left]\) 一定不等于 \(target\) 了，而 \(nums[left - 1]\) 可能是 \(target\)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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 # 计算机基础
下一页