526互联

[刷题技巧] 二分查找相关知识点汇总

发布时间 2023-12-21 15:20:07作者: Ac_c0mpany丶

二分搜索(binary search)算法

二分搜索算法，又名二分查找算法。
常用的使用场景：寻找一个数字、寻找左侧边界、寻找右侧边界

二分搜索模板

先介绍下二分搜索模板，后面的二分搜索都是基于这个二分搜索模板的

int binarySearch(int[] nums, int targer) {
	int left = 0, right = ...;  //思考1：right = nums.length还是right = nums.length - 1
	while(...){  // 思考2：left < right  还是 left <= right
		// left + right 可能会出现溢出
		int mid = left + (right - left) / 2;
		if (nums[mid] == target) return ...;
		else if (nums[mid] < target) left = ...;
		else if (nums[mid] > target) right = ...;
	} 
	return ...;
}

说明：

  1. 分析二分搜索代码时，不要出现else，全部展开成else if，方便理解。
  2. ... 的地方是需要详细说明的细节
  3. mid = (left + right) / 2写法中left +right可能出现溢出， 为了防止溢出可以写成：
mid = left + (right - left) / 2 # 偶数个元素 偏左
mid = left + (right - left + 1) / 2 # 偶数个元素 偏右
mid = left + ((right - left) >> 1)
mid = (left + right) >>> 1   # 无符号右移

寻找一个数(基本的二分搜索)

场景：搜索一个数，如果存在，则返回索引，否则返回-1。

在此之前，先简单提下搜索区间这个概念，二分搜索的变形一般分有左闭右闭和左闭右开两种搜索区间。

☆左闭右闭区间

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

首先 left 和 right 指针分别指向数组的首尾元素，都是可以取到的，我们称这个二分的搜索区间为左闭右闭区间，即[left, right]，这个区间其实就是每次进行搜索的区间，那么当区间为空的时候就终止搜索，那么啥时候区间刚好终止呢？答案是left = right + 1的时候，区间变为[right + 1， right]，这个区间为空。举个例子[2， 2]区间还存在数字2，而[3， 2]这个区间是不存在的。所以while的循环条件应该是left <= right，其终止条件正好是left == right + 1，区间为空（而不是left < right，它的终止条件是left == right 区间非空，区间中还存在一个元素）。下面开始搜索mid是否为查找的目标值，是就返回mid，不是就应该去掉mid分割成两个区间，而且应该保证这两个区间也是左闭右闭区间，那么只有分成[left， mid - 1] 和 [mid + 1， right]两种，这也就确定了后面left 和 right 的更新。当没搜索到目标值时，返回-1；

左闭右开区间

int binarySearch(int[] nums, int target){
    if(nums.size() == 0) return -1;
    int left = 0, right = nums.length; //注意 right
    while(left < right) { //注意 <
        int mid = mid = left + (right - left) / 2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) left = mid + 1; // 注意
        else if(nums[mid] > target) right = mid; //注意
    }
    //while循环的终止条件 left == right
    return -1;
}

首先 left 和 right 指针分别指向数组的首元素和末尾元素的后一位，显然right是取不到数组中元素的，我们称这个二分搜索区间为左闭右开区间， 即[left ，right)，这个区间其实就是每次进行搜索的区间，那么当区间为空的时候就终止搜索，那么啥时候区间刚好终止呢？答案是当left == right的时候，举个例子区间[2， 2）显然不存在。所以while循环条件应该是left < right，其终止条件正好是left == right，区间为空（为啥不是<=呢， 因为此时不是临界条件，不满足刚好停止）。下面开始搜索mid是否为查找的目标值，是就返回mid，不是就应该去掉mid分割成两个区间，而且应该保证这两个区间也是左闭右开区间，那么只有分割成[left，mid)和[mid + 1，right)，这也就确定了后面left 和 right 的更新。当没搜索到目标值时，返回-1；

但是上面两种算法存在局限性，比如，提供有序数组nums = [1, 3, 3, 3, 4]，target = 3，则该算法返回的是正中间的索引2。但是如果我们想找到target的左侧边界，即索引1，或者想找到target的右侧边，即索引3，则上述算法是无法处理的，下面就介绍算法的改进。

寻找左侧边界的二分搜索

查找第一个等于目标元素的下标

这里提供两种写法。

☆左闭右闭区间
int left_bound(int[] nums, int target) {
	if (nums == null || nums.length = 0) return -1;
	int left = 0, right = nums.length - 1; // 左闭右闭区间[left, right]
	while (left <= right) { //循环终止条件left == right + 1, [right+1, right]区间为空 
		int mid = left + (right - left) / 2;
		if (target == nums[mid]) {
			if (mid == 0 || nums[mid - 1] != target) {
				return mid;
			} else {
				right = mid - 1;	
			}	
		} else if (target < nums[mid]) {
			right = mid - 1;
		} else if (target > nums[mid]) {
			left = mid + 1;
		}
	}
	return -1;
}

说明：

  1. 能搜索左侧边界的关键在于
if (target == nums[mid]) {
	if (mid == 0 || nums[mid - 1] != target) {
		return mid;
	} else {
		right = mid - 1;	
	}	
}

找到target后不要立即返回，而是缩小搜索区间的上界right，在区间[left，mid - 1]中继续搜索，即不断地向左搜索，达到搜索左侧边界的目的。

  1. left和right更新的思路关键在于把握区间的切割，保证切割后的两个区间也是左闭右闭的。
左闭右闭区间
int left_bound(int[] nums, int target) {
	if (nums == null || nums.length = 0) return -1;
	int left = 0, right = nums.length; //左闭右开区间[left,right)
	while (left < right) { //循环终止条件left == right [right, right)区间为空
		int mid = left + (right - left) / 2;
		if (target = nums[mid]) {
			if (mid == 0 || nums[mid - 1] != target) {
				return mid;
			} else {
				right = mid;
			}
		} else if (target < nums[mid]) {
			left = mid + 1;
		} else if (target > nums[mid]) {
			right = mid;
		}
	}
	return -1;
}

说明：

  1. 当找到target时，不要立即返回，缩小区间的上界right，在区间[left，mid)中继续搜索。

查找第一个大于等于目标元素的下标

☆左闭右闭区间
int left_bound_eq(int[] nums, int target) {
	if (nums == null || nums.length = 0) return -1;
	int left = 0, right = nums.length - 1;
	while (left <= right) {
		if (target == nums[mid]) {
			if (mid == 0 || nums[mid - 1] < target) {
				return mid;
			} else {
				right = mid - 1;
			}
		} else if (target < nums[mid]) {
			if (mid == 0 || nums[mid - 1] < target) {
				return mid;
			} else {
				right = mid - 1;
			}	
		} else if (target > nums[mid]) {
			left = mid + 1;
		}
	}
	return -1;
}

将代码整理后：

int left_bound_eq(int[] nums, int target) {
	if (nums == null || nums.length = 0) return -1;
	int left = 0, right = nums.length - 1;
	while (left <= right) {
		if (target <= nums[mid]) {
			if (mid == 0 || nums[mid - 1] < target) return mid;
			else right = mid - 1;
			}
		}  else if (target > nums[mid]) {
			left = mid + 1;
		}
	}
	return -1;
}
左闭右开区间
int left_bound_eq(int[] nums, int target) {
	if (nums == null || nums.length = 0) return -1;
	int left = 0, right = nums.length;
	while (left < right) {
		if (target == nums[mid]) {
			if (mid == 0 || nums[mid - 1] < target) {
				return mid;
			} else {
				right = mid;
			}
		} else if (target < nums[mid]) {
			if (mid == 0 || nums[mid - 1] < target) {
				return mid;
			} else {
				right = mid;
			}	
		} else if (target > nums[mid]) {
			left = mid + 1;
		}
	}
	return -1;
}

整理之后：

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

寻找右侧边界的二分搜索

查找最后一个等于目标元素的下标

☆左闭右闭区间
int right_bound(int[] nums, int target) {
	if (nums.length == 0 || nums == null) return -1;
	int left = 0, right = nums.length - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (target == nums[mid]) {
			if (mid == nums.length - 1 || nums[mid + 1] != target) {
				return mid;
			} else {
				left = mid + 1;
			}
		} else if (target < nums[mid]) {
			right = mid - 1;
		} else if (target > nums[mid]) {
			left = mid + 1;
		}
	}
	return -1;
}
左闭右开区间
int right_bound(int[] nums, int target) {
	if (nums.length == 0 || nums == null) return -1;
	int left = 0, right = nums.length;
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (target == nums[mid]) {
			if (mid == nums.length - 1 || nums[mid + 1] != target) {
				return mid;
			} else {
				left = mid + 1;
			}
		} else if (target < nums[mid]) {
			right = mid;
		} else if (target > nums[mid]) {
			left = mid + 1;
		}
	}
	return -1;
}

查找最后一个小于等于目标元素的下标

☆左闭右闭区间
int right_bound_eq(int[] nums, int target) {
	if (nums.length == 0 || nums == null) return -1;
	int left = 0, right = nums.length - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (target == nums[mid]) {
			if (mid == nums.length - 1 || nums[mid + 1] > target) {
				return mid;
			} else {
				left = mid + 1;
			}
		} else if (target > nums[mid]) {
			if (mid == nums.length - 1 || nums[mid + 1] > target) {
				return mid;
			} else {
				left = mid + 1;
			}
		} else if (target < nums[mid]) {
			right = mid - 1;
		}
	}
	return -1;
}

int right_bound_eq(int[] nums, int target) {
	if (nums.length == 0 || nums == null) return -1;
	int left = 0, right = nums.length - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (target >= nums[mid]) {
			if (mid == nums.length - 1 || nums[mid + 1] > target) return mid;
			else left = mid + 1;
		} else if (target < nums[mid]) {
			right = mid - 1;
		}
	}
	return -1;
}
左闭右开区间
int right_bound_eq(int[] nums, int target) {
	if (nums.length == 0 || nums == null) return -1;
	int left = 0, right = nums.length;
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (target >= nums[mid]) {
			if (mid == nums.length - 1 || nums[mid + 1] > target) return mid;
			else left = mid + 1;
		} else if (target < nums[mid]) {
			right = mid;
		}
	}
	return -1;
}

总结

统一写成左闭右闭区间即可。

相关题目

  • LeetCode704. 二分查找
  • LeetCode34. 在排序数组中查找元素的第一个和最后一个位置
  • ~~LeetCode35. 搜索插入位置 ~~ 本质：找到第一个大于等于target的元素的下标
  • LeetCode4. 寻找两个正序数组的中位数 太难了
  • LeetCode74. 搜索二维矩阵

涉及搜索旋转排序数组：

  • LeetCode33. 搜索旋转排序数组
  • LeetCode81. 搜索旋转排序数组II
  • LeetCode153. 寻找旋转排序数组中的最小值
  • LeetCode154. 寻找旋转排序数组中的最小值II

关键：判断区间是否「连续递增」，只需比较区间边界值：如果 nums[left] <= nums[mid]，则区间 [left,mid] 连续递增；反之，区间 [mid,right] 连续递增。
?【LeetCode】33~154. 4 道「搜索旋转排序数组」题

涉及山脉数组：

  • LeetCode852. 山脉数组的顶峰索引 用mid和mid+1(或者mid-1)比较，排除不满足条件的元素
  • LeetCode162. 寻找峰值