二分查找专题

1490

1. 二分查找

关键词：有序的数组，都可以尝试使用二分查找

问题定义

给定一个由数字组成的有序数组 nums，并给你一个数字 target。问 nums 中是否存在 target。如果存在， 则返回其在 nums 中的索引。如果不存在，则返回 – 1

基本的二分查找

算法定义：将查找的键和子数组的中间键比较，如果被查找的键小于中间键，就在左子数组中继续查找，如果大于中间键，就在右子数组中查找，否则该键就是要找的元素
基本的算法要求数组元素有序且无重复元素
基本框架如下：

func binarySearch(src []int, target int) {
    for 未找到或没找完 {
        mid = left + (right - left) >> 1
        if src[mid] > target {
            在左子数组中继续查找
        } else if src[mid] < target {
            在右子数组中继续查找
        } else {
            找到了，返回
            return mid
        }
    }
    return -1
}
复制代码

二分查找变形

如果有重复元素，通过修改查找条件和返回值，也可以获取到自己想要的信息，核心在于：在有序的搜索区间内舍弃非法值

2. 技巧

循环不变量

即每一次边界的处理都按照区间的定义来操作

思维框架

  • 先定义搜索区间
  • 根据搜索区间定义循环结束条件
  • 取中间元素和目标元素做对比
  • 根据比较结果收缩区间，舍弃非法解
  • 跳出循环时，考虑清楚当前 l 和 r 值

3. 基本模板

左右封闭区间

定义 target 在区间 [left, right] 中，即 right 实际是能取到的值，所以写的时候时刻记住：

  1. 定义 right 时，可以取到，所以 len(nums)-1 
  2. 写 for 循环条件时，right 可以取到，left == right 的点有意义，需要判断，所以 left <= right
  • 更新 right 时，right 可以取到，前面的判断中，已经对 src[mid] 这个值进行过判断，下一轮可以不必再判断这个位置，所以下一次保持区间 [left, mid-1] ，所以 right 更新为 mid-1

模板为：

func binarySearch(nums []int, target int) int {
    // 1. r 的初始化
	l, r := 0, len(nums)-1
	// 把取的范围写在 for 上面提醒自己: [l,r]
	// 2. 循环条件 
	for l <= r {
		mid := l + (r-l)>>1
		if nums[mid] < target {
			l = mid + 1
		} else if nums[mid] > target {
			// 3. r 的变化
			r = mid - 1
		} else {
			return mid
		}
	}
	return -1
}
复制代码

167. 两数之和 II – 输入有序数组

// 双指针 + 二分
// 左边指针挨个遍历，右边指针二分去找差值
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        if idx := binarySearch(nums[i+1:], target - nums[i]); idx != -1 {
            return []int{i+1, idx+(i+1)+1}
        }
    }
    return []int{}
}
// 查找插入位置
func binarySearch(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] > target {
            r = mid - 1
        } else if nums[mid] < target {
            l = mid + 1
        } else {
            return mid
        }
    }
    return -1
}
复制代码

367. 有效的完全平方数

func isPerfectSquare(num int) bool {
    l, r := 1, num
    for l <= r {
        mid := l + (r-l) >> 1
        if mid * mid == num {
            return true
        } else if mid * mid < num {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return false
}
复制代码

374. 猜数字大小

/** 
 * 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
 * func guess(num int) int;
 */

func guessNumber(n int) int {
    l, r := 1, n
    for l <= r {
        mid := l + (r-l) >> 1
        cmp := guess(mid)
        if cmp == -1 {
            r = mid - 1
        } else if cmp == 1 {
            l = mid + 1
        } else {
            return mid
        }
    }
    return -1
}
复制代码

4. 常见变形

1. 寻找最左边满足条件的值

问题通常是，数组 [0,1,1,1,2,3,4] 中，找第一个出现 1 的位置
核心在于可能存在重复的数，那我们找到的 num[mid] == target 的 mid 只能当做”备胎”，再继续往左看看还有没有更合适的解
另外可能 l 会越界，跳出前需要判断是否越界

func binarySearch(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        // 等于也需要往左找
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    // 注意判断条件，l 取不到 len(nums)，所以是 l >= len(nums)
    if l >= len(nums) || nums[l] != target {
        return -1
    }
    // 由于相等是往左边找，缩的 r，l 是备胎，最终返回 l
    return l
}
复制代码

1351. 统计有序矩阵中的负数

关键词：二维数组的行按非递增顺序排列
对二维数组的每行使用二分，查找 target 为 0 的最右区间，另外通常都是从小到大，这道题是从大到小排序，反着排除非法区间即可

// 查找 target 为 0 的最右区间
func countNegatives(grid [][]int) int {
    ans := 0
    for _, src := range grid {
        idx := binarySearch(src, 0)
        ans += len(src) - idx
    }
    return ans
}
func binarySearch(src []int, target int) int {
    // [l, r]
    l, r := 0, len(src) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if src[mid] < target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l
}
复制代码

69. x 的平方根

平方根特殊处理，小的有可能就是答案，所以提前记录下列

func mySqrt(x int) int {
    // [l, r]
    l, r := 0, x
    ans := 0
    for l <= r {
        mid := l + (r-l) >> 1
        if mid * mid > x {
            r = mid - 1
        } else if mid * mid == x {
            return mid
        } else {
            ans = mid
            l = mid + 1
        }
    }
    return ans
}
复制代码

278. 第一个错误的版本

当返回为 true，还继续往左边查看有没有更合适的解

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return 	 	      true if current version is bad 
 *			          false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    l, r := 1, n
    for l <= r {
        mid := l + (r-l) >> 1
        if isBadVersion(mid) {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l
}
复制代码

441. 排列硬币

和找平方根类似，可能在找更小值时把答案弄丢了，所以记录一下

func arrangeCoins(n int) int {
    l, r := 1, n
    ans := 0
    for l <= r {
        mid := l + (r-l) >> 1
        sum := (1 + mid) * mid / 2
        if sum <= n {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}
复制代码

875. 爱吃香蕉的珂珂

/* 二分，速度区间为 [1,sum]
   寻找最左满足条件
*/
func minEatingSpeed(piles []int, h int) int {
    sum := 0
    for _, v := range piles {
        sum += v
    }
    l, r := 1, sum
    for l <= r {
        mid := l + (r-l) >> 1
        if check(piles, h, mid) {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l
}
func check(piles []int, h, speed int) bool {
    hour := 0
    for _, v := range piles {
        hour += int(math.Ceil(float64(v)/float64(speed)))
    }
    return hour <= h
}
复制代码

2. 寻找最右边满足条件的值

和寻找最左边满足条件的值类似，当相等了，可以再往右看看还有没有
其模板如下：

func binarySearch(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        // 相等了，再往右看看
        if nums[mid] <= target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    // 注意条件，r 是往左走的，所以最后是判断 r < 0 越界
    if r < 0 || nums[r] != target {
        return -1
    }
    // 由于相等是向右，l 变化，r 是备胎
    return r
}
复制代码

寻找最左满足条件和最右满足条件的区别：

  1. 当相等时，备胎不同，寻找最左就是往左继续去找，寻找最右就是往右继续去找
  2. 由于备胎不同，跳出后的判断也是对不同备胎判断的，所以范围不同
  3. 最后返回的备胎也不同

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

// 寻找最左最右满足条件
func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1,-1}
    }
    left := LeftBinarySearch(nums, target)
    right := rightBinarySearch(nums, target)
    return []int{left, right}
}
func LeftBinarySearch(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    if l >= len(nums) || nums[l] != target {
        return -1
    }
    return l
}
func rightBinarySearch(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] > target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    if r < 0 || nums[r] != target {
        return -1
    }
    return r
}
复制代码

3. 寻找最左插入位置

问题通常是，数组 [1,2,4] 中，target 为 3，如果找不到 target，返回 target 应该插入的位置，使数组依然保持有序；如果有多个满足条件的值，应该返回最左侧的，例如 [1,4,4,4,4,4]，target 为 4，应该插入的位置是 1
和前面不同的是，寻找最左边的满足条件的值是在相同数中往左边找备胎，寻找最左插入位置，那大于等于这个数的值都可以作为答案的”备胎”，当遇到”备胎”，需要继续再往左看看还有没有更合适的解
最终跳出循环时，l 就是当前最好的备胎，返回 l 即可
其中，跳出循环时，l 的含义是”小于要插入值的个数”
（寻找最右插入位置同理）

func binarySearch(nums []int, target int) int {
	// 1. r 的初始化
	l, r := 0, len(nums)-1
	// 把取的范围写在 for 上面提醒自己: [l,r]
	// 2. 循环条件
	for l <= r {
		mid := l + (r-l)>>1
        // 大于等于这个数，继续往左找备胎
		if nums[mid] >= target {
			// 3. r 的变化
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
    // l 就是此时最好的备胎
	return l
}
复制代码

35. 搜索插入位置

和模板一样

func searchInsert(nums []int, target int) int {
    // [l, r]
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l
}
复制代码

744. 寻找比目标字母大的最小字母

// 寻找最右边插入位置的值
// 特殊点：如果等于，往右找
func nextGreatestLetter(letters []byte, target byte) byte {
    l, r := 0, len(letters)
    for l < r {
        mid := l + (r-l) >> 1
        if letters[mid] <= target {
            l = mid + 1
        } else {
            r = mid
        }
    }
    // l 的含义是"小于等于要插入数的个数"
    return letters[l%len(letters)]
}
复制代码

658. 找到 K 个最接近的元素

// 找到最左插入位置，再向两边走寻找足够的数
func findClosestElements(arr []int, k int, x int) []int {
    ans := make([]int, 0, k)
    // res 可能和 x 差 0，也可能差更多
    res := search(arr, x)
    l, r := res-1, res
    for len(ans) < k {
        // 加左边
        if l >= 0 && (r == len(arr) || abs(arr[l]-x) <= abs(arr[r]-x)) {
            ans = append(ans, arr[l])
            l--
        } else {
            // 否则加右边
            ans = append(ans, arr[r])
            r++
        }
    }
    // 结果再排序
    sort.Ints(ans)
    return ans
}
func search(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
复制代码

4. 局部有序

问题通常是，在局部有序数组中查找某个值，数组可能是先降后升，或者先升后降，例如 [5,6,7,1,2,3,4]，这种情况下需要去比较当前 [l,r] 区间是在该数组的哪个部分
之前都是使用 target 和 src[arr] 做比较，其实我们还可以通过借助例如 arr[l], arr[r], arr[0], arr[len(arr)-1], arr[mid-1], arr[mid+1] 的情况来辅助判断当前搜索区间是什么情况，根据情况分析需要舍弃哪一半的非法解
想办法寻找有序的区间，在有序的区间内进行判断

33. 搜索旋转排序数组

func search(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] == target {
            return mid
        } else if nums[l] <= nums[mid] {
            // target 在 [l, mid) 中，砍去后半段
            if nums[l] <= target && target < nums[mid] {
                r = mid - 1
            } else {
                l = mid + 1
            }
        } else {
             // target 在 (mid, r] 中，砍去前半段
            if nums[mid] < target && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }
    return -1
}
复制代码

81. 搜索旋转排序数组 II

可能存在重复项，只能通过一项一项排除干扰项

func search(nums []int, target int) bool {
    l, r := 0, len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] == target {
            return true
        }
        // 出现重复项没办法，只有通过遍历排除干扰项
        for l < mid && nums[l] == nums[mid] {
            l++
        }
        if nums[l] <= nums[mid] {
            if nums[l] <= target && target < nums[mid] {
                r = mid - 1
            } else {
                l = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }
    return false
}
复制代码

5. 寻找最值

二分法查找最值，需要始终将最值套在区间内，不断收缩左右边界
即使是查找最值，也至少范围内有序才能找到

153. 寻找旋转排序数组中的最小值

l, r, mid (位置)的值只有三种情况：

  1. l 最小，例如 [1,2,3]，l < mid, mid < r，收缩右边
  2. mid 最小，例如 [3,1,2], l > mid, mid < r，收缩右边，但不能把 mid 给缩没了
  3. r 最小，例如 [2,3,1]，l < mid, mid > r，收缩左边

只有选择 mid > r，进这个判断收缩左边，不进这个判断收缩右边，还不能把 mid 缩没了，所以只能 r = mid
当最后搜索区间只剩一个，会一直收缩右边，导致 r = l，且 r 不变，所以循环条件只能是 l < r ，另外这个搜索区间就是最小值，所以返回 nums[l] 和 nums[r] 一样

func findMin(nums []int) int {
    l, r := 0, len(nums) - 1
    for l < r {
        mid := l + (r-l) >> 1
        if nums[mid] > nums[r] {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return nums[l]
}
复制代码

162. 寻找峰值

既然有左右两边兜底，那沿着一个坡，肯定能找到最值

func findPeakElement(nums []int) int {
    l, r := 0, len(nums) - 1
    for l < r {
        mid := l + (r-l) >> 1
        if nums[mid] > nums[mid+1] {
            r = mid
        } else {
            l = mid + 1
        }   
    }
    return l
}
复制代码

852. 山脉数组的峰顶索引

问题在于，需要判断当前是在上坡还是下坡
mid 和 mid+1 比较，沿着上坡的路，肯定会有峰顶

func peakIndexInMountainArray(arr []int) int {
    l, r := 0, len(arr) - 1
    for l < r {
        mid := l + (r-l) >> 1
        if arr[mid] > arr[mid+1] {  // 下坡
            r = mid 
        } else {
            l = mid + 1
        }
    }
    return l
}
复制代码
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
后端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4202
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3895
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
相关推荐
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
Integer的最大值是什么？｜ Java Debug 笔记-一一网
Integer的最大值是什么？｜ Java Debug 笔记
Integer的最大值是什么？｜ Java Debug 笔记
4年前 2767
使用arthas trace命令查看代码各方法响应时间-一一网
使用arthas trace命令查看代码各方法响应时间
使用arthas trace命令查看代码各方法响应时间
4年前 2722
Spring Boot集成Druid异常discard long time none received connection.-一一网
Spring Boot集成Druid异常discard long time none received connection.
Spring Boot集成Druid异常discard long time none received connection.
4年前 2137
pandas系列之导出为.csv文件-一一网
pandas系列之导出为.csv文件
pandas系列之导出为.csv文件
4年前 2109
使用XXL-JOB时，如何避免多台服务器重复调度任务？｜工作踩坑系列-一一网
使用XXL-JOB时，如何避免多台服务器重复调度任务？｜工作踩坑系列
使用XXL-JOB时，如何避免多台服务器重复调度任务？｜工作踩坑系列
4年前 1681
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云