Week 44 @ 2024 算法周记【二分查找】
- Bryan
二分查找
LC 704. Binary Search 二分查找
https://leetcode.com/problems/binary-search/
给定一个【有序】【不重复】数组和一个目标值，找到这个元素的索引；如果不存在，返回 -1
func search(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else { // nums[mid] > target
right = mid
}
}
return -1 // not found
}一般算法中使用的都是 [left, right) 区间
二分查找【寻找左侧边界】
给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1
func searchLeft(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
// 此时 left=right
// 算法核心思想为【持续收缩右边界至 >= target 的最小索引】
// -> 如果 target < min(nums) 返回 0
// -> 如果 target > max(nums) 返回 len(nums)
if right >= len(nums) || nums[right] != target {
// NOTE: 此时 right 是【大于 target 的最小索引】
// 例如：[1, 3, 5, 7] target=4
// 返回的是 2 <- 指向了 5
return -1
}
return right
}可利用牛客进行测试：https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9
二分查找【寻找右侧边界】
给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1
方法一
整体思路刚好与 searchLeft 相反，为收缩左边届 ——
方法二：利用 leftBound
上一题的 searchLeft 中其实隐含了一个「找到 >= target 的最小索引」的方案（称为 leftBound）
利用 leftBound 可知，找到「== x 的最右侧索引」问题可以转换为找到「>= x+1 的最左侧索引再 -1」即 leftBound(target+1)-1
LC.34 Find. First and Last Position of Element in Sorted Array 在排序数组中找元素的第一个和最后一个位置【寻找左右边界】
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
利用 leftBound 完成 ：
LCCN LCR 172. 统计目标成绩的出现次数
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/
本题与上一题几乎一样（只有返回值不一样）
采用 rightBound 完成：
LC.278 First Bad Version 第一个错误的版本
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/