【算法思想04】二分查找

1. 基本思想与实现

1.1 基本思想

二分查找是一种在有序数组中查找目标元素的算法，又称折半查找。

通过将数组分成两部分，并比较目标元素与数组中间元素的大小，来确定目标元素在哪一部分中。

• 如果目标元素等于中间元素，则查找成功。
• 如果目标元素小于中间元素，则在左半部分继续查找。
• 如果目标元素大于中间元素，则在右半部分继续查找。

重复这个过程，直到找到目标元素或确定目标元素不存在。

Input : [1,2,3,4,5]
target : 3
return the index : 2

1.2 值m的计算方式

• m = (l + h) / 2，可能出现加法溢出，即l+h的结果超出整型的表示范围。
• m = l + (h - l) / 2，建议使用。

1.3 查找失败时的返回值

循环退出时如果仍然没有查找到target，那么表示查找失败。可以有两种返回值：

• -1：以一个错误码表示没有查找到target
• l：将target插入到nums中的正确位置

1.4 代码实现

1.4.1 循环

框架：

public int binarySearch(int[] nums, int target) {int l = 0, h = ...;while (...) {int m = l + (h - l) / 2;if (nums[m] == target) {	//	查找成功...} else if (nums[m] > target) {	//	查找左半区间h = ...;} else if (nums[m] < target) {	//	查找右半区间l = ...;}}return ...;
}

基本实现：

public int binarySearch(int[] nums, int target) {//	1. 设置查找区间int l = 0, h = nums.length - 1;//	2. 若查找区间[l, h]不存在，则查找失败while (l <= h) {//	3. 取中间元素nums[m]与目标元素target比较大小int m = l + (h - l) / 2;if (nums[m] == target) {	//	3.1 查找成功return m;} else if (nums[m] > target) {	//	3.2 查找左半区间h = m - 1;} else {	//	3.3	查找右半区间l = m + 1;}}return -1;
}

1.4.2 递归

基本实现：

public int recursiveBinarySearch(int[] nums, int l, int h, int target) {//	1. 若查找区间[l, h]不存在，则查找失败if (l > h) return -1;//	2. 取中间元素nums[m]与目标元素target比较大小int m = l+ (h - l) / 2;if (nums[m] == target) {	//	2.1 查找成功return m;} else if (nums[m] > target) {	//	2.2 查找左半区间return recursiveBinarySearch(l, m-1, nums, target);} else {	//	2.3	查找右半区间return recursiveBinarySearch(m+1, h, nums, target);}
}

2. 性能分析

2.1 时间复杂度

二分查找的时间复杂度取决于查找成功或失败的情况。

在最好情况下，即目标元素恰好是数组中间元素，只需要进行1次比较就能找到目标元素，时间复杂度为O(1)。

在最坏情况下，即查找不到目标元素，需要进行log2(n)次比较，其中n是数组的长度，时间复杂度为O(log n)。

平均情况下，二分查找的时间复杂度也是O(log n)。

2.2 与顺序查找的效率比较

顺序查找的平均时间复杂度为O(n)，因此二分查找性能更优。

3. 应用

3.1 前提

二分查找只适用于有序数组。如果数组无序，需要先进行排序操作，然后再进行二分查找。

3.2 变体

3.2.1 最基本的二分查找

• 初始化h = nums.length - 1;
• 查找区间[l, h]
• 循环终止条件while (l <= h)
• 区间收缩l=m+1;或h=m-1;
• 当nums[m] == target时可立即返回

局限性：对nums = [1, 3, 3, 3, 4]和target = 3的情况，会返回索引2，无法求得target的左侧边界1和右侧边界3。

3.2.2 寻找左侧边界的二分查找

• 初始化h = nums.length;
• 查找区间[l, h)
• 循环终止条件while (l < h)
• 区间收缩l=m+1;或h=m;
• 当nums[m] == target时不要立即返回，收缩右侧边界以锁定左侧边界，返回left

3.2.3 寻找右侧边界的二分查找

• 初始化h = nums.length;
• 查找区间[l, h)
• 循环终止条件while (l < h)
• 区间收缩l=m+1;或h=m;
• 当nums[m] == target时不要立即返回，收缩左侧边界以锁定右侧边界。因收缩左侧边界执行了l = m + 1，因此返回左侧边界时需要-1；因查找区间为左闭右开，因此返回右侧边界时也需要-1。

查找区间的开闭情况、循环终止条件是否包含等号都取决于h的初始化值。

3.2.4 三种二分查找的实现代码

public int binarySearch(int[] nums, int target) {int l = 0, h = nums.length - 1;while (l <= h) {int m = l + (h - l) / 2;if (nums[m] == target) {// 直接返回return m;} else if (nums[m] > target) {h = m - 1;} else {l = m + 1;}}// 直接返回return -1;
}public int leftBound(int[] nums, int target) {int l = 0, h = nums.length - 1;while (l <= h) {int m = l + (h - l) / 2;if (nums[m] == target) {// 不返回，收缩右边界，锁定左边界h = m - 1;} else if (nums[m] > target) {h = m - 1;} else {l = m + 1;}}// 检查l越界的情况if (l >= nums.length || nums[l] != target) return -1;return l;
}public int rightBound(int[] nums, int target) {int l = 0, h = nums.length - 1;while (l <= h) {int m = l + (h - l) / 2;if (nums[m] == target) {// 不返回，收缩左边界，锁定右边界l = m + 1;} else if (nums[m] > target) {h = m - 1;} else {l = m + 1;}}// 检查r越界的情况if (r < 0 || nums[r] != target) return -1;return r;
}

3.3 注意事项

• 边界值的判断，例如h=m-1还是h=m等
• 查找区间的开闭情况，l和h的更新完全取决于查找的区间
• 循环终止条件，例如应该使用l<h还是l<=h等
• 返回值，例如应该返回l、返回m、还是返回h等

4. 例题

以下例题的题解皆使用基于循环的二分查找实现。

4.1 二分查找（704简单）

4.2 X的平方根（69简单）

即使用二分查找在区间[0,x]中查找x的平方根

class Solution {public int mySqrt(int x) {if (x <= 1) return x;int l = 1, h = x;while (l <= h) {int m = l + (h-l) / 2;if (x/m == m) {	// 使用m*m会溢出return m;} else if (x/m < m) {   // target in [l, m-1]h = m - 1;} else {    // target in [m+1, h]l = m + 1;}}return h;   // 退出循环的条件是l>h，所以此时h总是小于l的，因此返回h而不是返回l}
}

4.3 寻找比目标字母大的最小字母（744简单）

class Solution {public char nextGreatestLetter(char[] letters, char target) {int l = 0, h = letters.length - 1;while (l <= h) {if (letters[l] > target) return letters[l];int m = l + (h-l) / 2;if (letters[m] <= target) {	// target in [m+1, h]l = m + 1;} else {	// target in [l, m]h = m;}}return letters[0];}
}

4.4 有序数组中的单一元素（540中等）

令target为单一元素在数组中的位置
在target之后，数组中原来存在的成对状态被改变如果m为偶数
当m + 1 < index，有nums[m] == nums[m+1]
当m + 1 >= index，有nums[m] != nums[m+1]

class Solution {public int singleNonDuplicate(int[] nums) {int l = 0,h = nums.length - 1;while (l < h) {// 保证l、m、h都在偶数位，使得查找区间的长度为奇数if (m % 2 == 1) m--;if (nums[m] == nums[m+1]) { // target in [m+2, h]l = m + 2;} else {    // target in [l, m]h = m;}}// l=h，不返回nums[m]return nums[l];}
}

4.5 第一个错误的版本（278简单）

使用二分查找，找到[false,false,...,false,true,true,...true]中第一个true的下标

/* The isBadVersion API is defined in the parent class VersionControl.boolean isBadVersion(int version); */public class Solution extends VersionControl {public int firstBadVersion(int n) {int l = 1, h = n;while (l <= h) {int m = l + (h-l) / 2;if (isBadVersion(m)) {  // target in [l, m-1]h = m - 1;} else {    // target in [m+1, h]l = m + 1;}}return l;}
}

4.6 寻找旋转排序数组中的最小值（153中等）

class Solution {public int findMin(int[] nums) {int l = 0, h = nums.length-1, m=0;while (l < h) {m = l + (h-l) / 2;if (nums[m] > nums[h]) {   // target in [m+1, h]l = m + 1;} else {    // target in [l, m]h = m;}}return nums[l];}
}

4.7 在排序数组中查找元素的第一个和最后一个位置（34中等）

使用二分查找的方式缩小区间，查找数组nums中元素的值都为target的子区间[l, h]

class Solution {public int[] searchRange(int[] nums, int target) {int l = 0, h = nums.length - 1;while (l <= h) {int m = l + (h-l) / 2;if (nums[m] < target) { // target in [m+1,h]l = m + 1;} else if (nums[m] > target) {  // target in [l,m-1]h = m - 1;} else {    // nums[m] == targetif (nums[l] == nums[h]) {if (nums[l] == target) return new int[]{l,h};else return new int[]{-1,-1};}if (nums[l] < target) l++;if (nums[h] > target) h--;}}return new int[]{-1,-1};}
}

4.8 寻找峰值（162中等）

对于所有有效的 i 都有 nums[i] != nums[i + 1]
.
由提示知相邻元素的值不相等，寻找数组中的极大值（该值也可能是边界值）
input: [1,2,3] - > output: 2

class Solution {public int findPeakElement(int[] nums) {int l = 0, h = nums.length - 1;while (l < h) {int m = l + (h-l) / 2;if (nums[m] < nums[m+1]) {  // target in [m+1, h]l = m + 1;} else {   // target in [l, m]h = m;}}return l;}
}

4.9 修车最少时间（2594中等）

枚举时间 t 能都修完所有汽车。假设最少时间为 t，则
时间大于等于 t 都可以修完，否则都修不完，所以 t 的值域具有单调性，可以枚举 t 并使用二分查找。
.
在ranks[i]*n^2的时间内可以修完n辆车 -> 机械工i的效率为1/ranks[i]
随机取一个机械工修完所有车的时间作为上界

class Solution {public long repairCars(int[] ranks, int cars) {long left = 0, right = 1l * ranks[0]*cars*cars; // 防止溢出long mid = 0;while (left < right) {mid = left + (right - left) / 2;if (check(ranks, cars, mid)) {  // 判断mid分钟内机械工们能否修完carsright = mid;    // 能修完。移动上界} else {left = mid + 1; // 修不完。移动下界}}return left;    // 一定是执行left=mid+1后才跳出循环的}private boolean check(int[] ranks, int cars, long mid) {long cnt = 0;for (int x : ranks) {   // 累计每个机械工在mid分钟内修完的汽车数目cnt += (long) Math.sqrt(mid / x);}return cnt >= cars;}
}

参考资料

• Leetcode 题解 - 二分查找
• 图文并茂带你入门二分查找算法
• labuladong的算法小抄 - 我写了首诗，把二分搜索算法变成了默写题

撰写于2024年1月16日凌晨2时