前言
由于我在学习二分查找的过程中处于会了忘,忘了复习的状态,因此总结一套适合自己记忆的模板。建议先看参考资料\(^{[1,2,3]}\),理解二分查找各种细节的由来。
左闭右开的形式:循环条件一定是
while(left < right)
。由于左闭,所以left = mid + 1;
。由于右开,所以right = mid;
。最后循环结束时,left == right
。左闭右闭的形式:循环条件一定是
while(left <= right)
。由于左闭,所以left = mid + 1;
。由于右闭,所以right = mid - 1;
。最后循环结束时,left == right + 1
。
确保上面段话能理解,为了方便记忆,优先采用左闭右开的形式。因为循环结束时,
left == right
,我觉得简单一点。
基础的二分查找
力扣链接:704. 二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
左闭右开代码实现
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length; // 定义target在左闭右开的区间里,即:[left, right)
while(left < right){ // 因为left == right的时候,在[left, right)是空区间,所以使用小于号
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else if(nums[mid] > target){
right = mid; // target 在左区间,在[left, mid)中
}else{ // nums[mid] == target
return mid; // 数组中找到目标值,直接返回下标
}
}
return -1; // 未找到目标值
}
}
左闭右闭代码实现
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1; // // 定义target在左闭右开的区间里,即:[left, right)
while(left <= right){ // 因为left == right的时候,在[left, right]还有一个元素,所以使用小于等于号
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right]中
}else if(nums[mid] > target){
right = mid - 1; // target 在左区间,在[left, mid - 1]中
}else{
return mid; // // 数组中找到目标值,直接返回下标
}
}
return -1; // 未找到目标值
}
}
lower_bound 和 upper_bound
lower_bound
lower_bound
含义:
- 返回第一个大于等于 target 的位置,如果所有元素都小于 target,则返回数组的长度。
- 在不改变原有排序的前提下,找到第一个可以插入 target 的位置。
左闭右开代码实现
int lower_bound(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){ // 定义target在左闭右开的区间里,即:[left, right)
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else{
right = mid; // target 在左区间,在[left, mid)中
}
}
return left; // 此时 left == right,返回 right 也可以
}
对于 nums[mid] == target
的情况:
此时找到一个目标值 target,然而左边可能还有 target。由于要找的是第一个大于等于 target 的位置,所以应该向左区间继续查找,因此与 else
分支合并。
左闭右闭代码实现
int lower_bound(int[] nums, int target){
int left = 0, right = nums.length - 1;
while(left <= right){ // 定义target在左闭右闭的区间里,即:[left, right]
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right]中
}else{
right = mid - 1; // target 在左区间,在[left, mid - 1]中
}
}
return left; // 此时 left == right + 1
}
这里和左闭右开形式不同,左闭右开 left == right
,不用纠结。这里 left == right + 1
,有时候搞不清楚是返回 left
,right
,还是 left - 1
......
这里有个方便记忆的小技巧,假设 left
和 right
都指向 target
,再看下一步的结果。
比如下面这个例子,target == 3
,lower_bound
要求的结果就是红色的3。
![](/i/l/?n=23&i=blog/3053504/202301/3053504-20230116163059713-1504739273.png)
此时 left == right
,根据代码,应该执行 right = mid - 1;
这条语句,执行之后,如下图所示。
![](/i/l/?n=23&i=blog/3053504/202301/3053504-20230116163534735-494686315.png)
此时,left == right + 1
,循环结束,结果应该为 left
,所以 return left;
。
upper_bound
upper_bound
含义:
- 返回第一个大于 target 的位置,如果所有元素都小于等于 target,则返回数组的长度。
- 在不改变原有排序的前提下,找到最后一个可以插入 target 的位置。
左闭右开代码实现
int upper_bound(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){ // 定义target在左闭右开的区间里,即:[left, right)
int mid = left + (right - left) / 2;
if(nums[mid] <= target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else{
right = mid; // target 在左区间,在[left, mid)中
}
}
return left; // 此时 left == right,返回 right 也可以
}
对于 nums[mid] == target
的情况:
此时找到一个目标值 target。由于要找的是第一个大于 target 的位置,所以应该向右区间继续查找,所以与 if
分支合并。
左闭右闭代码实现
int upper_bound(int[] nums, int target){
int left = 0, right = nums.length - 1;
while(left <= right){ // 定义target在左闭右闭的区间里,即:[left, right]
int mid = left + (right - left) / 2;
if(nums[mid] <= target){
left = mid + 1; // target 在右区间,在[mid + 1, right]中
}else{
right = mid - 1; // target 在左区间,在[left, mid - 1]中
}
}
return left; // 此时 left == right + 1
}
和 lower_bound
类似,说一下记忆 return left;
的技巧。
假设 left
和 right
都指向 target
,再看下一步的结果。
比如下面这个例子,target == 3
,upper_bound
要求的结果就是红色的4。
![](/i/l/?n=23&i=blog/3053504/202301/3053504-20230116165121465-1055388439.png)
此时 left == right
,根据代码,应该执行 left = mid + 1;
这条语句,执行之后,如下图所示。
![](/i/l/?n=23&i=blog/3053504/202301/3053504-20230116165240523-1780568878.png)
此时,left == right + 1
,循环结束,结果应该为 left
,所以 return left;
。
可以看到,在左闭右闭的情况下,lower_bound
和 upper_bound
都返回 left
。
lower_bound 和 upper_bound 的联系
可以发现,这两个函数只有 if
判断为相等的情况不同[6]。为方便记忆,在 if else
只有二分支的情况下,即把相等的情况归为 if
分支或 else
分支(不是 if ... else if ... else ...
三分支的情况)。
此时,lower_bound
和 upper_bound
可以通过在 if
分支判断语句中增删 =
互相转化。
另外,upper_bound
可以直接复用 lower_bound
。
对于非递减整数数组,\(>x\) 等价于 \(\geq x+1\)[1],upper_bound
求第一个大于 target 的位置,就等价于 lower_bound
求第一个大于等于 target + 1 的位置。
因此,upper_bound
的另一种写法
int upper_bound(int[] nums, int target){
return lower_bound(nums, target + 1);
}
所以,只要记 lower_bound
的代码就好了。
力扣相关题目
35. 搜索插入位置
力扣链接:35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
解法一
直接应用 lower_bound
class Solution {
public int searchInsert(int[] nums, int target) {
return lower_bound(nums, target);
}
int lower_bound(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){ // 定义target在左闭右开的区间里,即:[left, right)
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else{
right = mid; // target 在左区间,在[left, mid)中
}
}
return left; // 此时 left == right,返回 right 也可以
}
}
解法二
通过 upper_bound
转化
class Solution {
public int searchInsert(int[] nums, int target) {
int pos = upper_bound(nums, target);
if(pos == 0 || nums[pos - 1] != target) return pos; // target 不存在
return pos - 1; // target 存在,前一个位置就是 target
}
int upper_bound(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){ // 定义target在左闭右开的区间里,即:[left, right)
int mid = left + (right - left) / 2;
if(nums[mid] <= target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else{
right = mid; // target 在左区间,在[left, mid)中
}
}
return left; // 此时 left == right,返回 right 也可以
}
}
直接记解法一就行了,解法二只是证明 upper_bound
也可以做,因为 lower_bound
和 upper_bound
本来就有转化关系。
34. 在排序数组中查找元素的第一个和最后一个位置
力扣链接:34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
思路
第一个位置:就是 lower_bound
函数的含义。
最后一个位置:如果 target 存在的话,第一个大于 target 的位置减一就是 target 的最后一个位置。
代码实现
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = lower_bound(nums, target);
if(start == nums.length || nums[start] != target) return new int[]{-1, -1}; // target 不存在
int end = upper_bound(nums, target) - 1;
return new int[]{start, end};
}
int lower_bound(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){ // 定义target在左闭右开的区间里,即:[left, right)
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else{
right = mid; // target 在左区间,在[left, mid)中
}
}
return left; // 此时 left == right,返回 right 也可以
}
int upper_bound(int[] nums, int target){
return lower_bound(nums, target + 1);
}
}
69. x 的平方根
力扣链接:69. x 的平方根
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意: 不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
思路
这其实就是一个 upper_bound
问题,对于 x = 8
,二分区间应该在 [0,8]
,我们要在这些数的平方中找到第一个大于8的数,它左边的那个数的平方根就是答案。如下图所示,找到9(是第一个大于8的数),左边4的平方根2就是答案。
![](/i/l/?n=23&i=blog/3053504/202301/3053504-20230116173038043-1720273343.png)
代码
直接应用 upper_bound
,下面的代码会超出内存限制,但是方便我们理解它和 upper_bound
的关系。
class Solution {
public int mySqrt(int x) {
int[] nums = new int[x + 1];
for(int i = 0; i <= x; i++) nums[i] = (i + 1) * (i + 1);
int res = upper_bound(nums, x);
return res;
}
int lower_bound(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){ // 定义target在左闭右开的区间里,即:[left, right)
int mid = left + (right - left) / 2;
if(nums[mid] < target){
left = mid + 1; // target 在右区间,在[mid + 1, right)中
}else{
right = mid; // target 在左区间,在[left, mid)中
}
}
return left; // 此时 left == right,返回 right 也可以
}
int upper_bound(int[] nums, int target){
return lower_bound(nums, target + 1);
}
}
左闭右开代码
由于 x + 1
可能溢出,所以要用 long
。
class Solution {
public int mySqrt(int x) {
long left = 0, right = (long) x + 1; //左闭右开,所以是[0,x+1)
while(left < right){
long mid = left + (right - left) / 2;
if(f(mid) <= x){
left = mid + 1;
}else{
right = mid;
}
}
return (int)(left - 1);
}
long f(long x){ // 计算x的平方
return (long) x * x;
}
}
左闭右闭代码
class Solution {
public int mySqrt(int x) {
int left = 0, right = x; //左闭右闭,所以是[0,x]
while(left <= right){
int mid = left + (right - left) / 2;
if(f(mid) <= x){
left = mid + 1;
}else{
right = mid - 1;
}
}
return left - 1;
}
long f(int x){ // 计算x的平方
return (long) x * x;
}
}
367. 有效的完全平方数
力扣链接:367. 有效的完全平方数
给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数,如 sqrt 。
示例 1:
输入:num = 16
输出:true
解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。
示例 2:
输入:num = 14
输出:false
解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
左闭右开代码
由于 x + 1
可能溢出,所以要用 long
。
class Solution {
public boolean isPerfectSquare(int num) {
long left = 1, right = num + 1; //左闭右开,所以是[0,x+1)
while(left < right){
long mid = left + (right - left) / 2;
long square = mid * mid;
if(square < num){
left = mid + 1;
}else if(square > num){
right = mid;
}else{
return true;
}
}
return false;
}
}
左闭右闭代码
class Solution {
public boolean isPerfectSquare(int num) {
int left = 1, right = num; //左闭右闭,所以是[0,x]
while(left <= right){
int mid = left + (right - left) / 2;
long square = (long) mid * mid;
if(square < num){
left = mid + 1;
}else if(square > num){
right = mid - 1;
}else{
return true;
}
}
return false;
}
}
二分查找进阶
以上是基础的二分查找类型,对于进阶的题目,把问题转化成二分查找是一个难点。
参考资料
- 二分查找又死循环了?【基础算法精讲 04】
- 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找
- 我写了首诗,让你闭着眼睛也能写对二分搜索
- C++中的upper_bound和lower_bound区别
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 用Java实现C++::std中的upper_bound和lower_bound
以上是我个人的学习心得,能力有限,如有错误和建议,恳请批评指正!
标签:二分,总结,right,target,nums,int,mid,查找,left From: https://www.cnblogs.com/dotJunz/p/17050683.html