二分查找
LC 704. Binary Search 二分查找
https://leetcode.com/problems/binary-search/
给定一个【有序】【不重复】数组和一个目标值，找到这个元素的索引；如果不存在，返回 -1
| Code Block |
|---|
|
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) 区间
| Expand |
|---|
| title | 如果想要 [left, right] 区间的话 |
|---|
|
| Code Block |
|---|
| func search(nums []int, target int) int {
left, right := 0, len(nums)-1
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 - 1
}
}
return -1 // not found
} |
|
二分查找【寻找左侧边界】
给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1
| Code Block |
|---|
|
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
| Code Block |
|---|
|
class BinarySearch {
public:
int getPos(vector<int> nums, int n, int target) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (right >= n || nums[right] != target) {
return -1;
}
return right;
}
}; |
二分查找【寻找右侧边界】
给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1
方法一
| Code Block |
|---|
func searchRight(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] <= target {
left = mid + 1
} else if nums[mid] > target {
right = mid
}
}
// 算法核心思想为【持续收缩左边界至 <= target 的最大索引 + 1】
if left <= 0 {
return -1
}
return left - 1
}
|
整体思路刚好与 searchLeft 相反，为收缩左边届 ——
方法二：利用 leftBound
上一题的 searchLeft 中其实隐含了一个「找到 >= target 的最小索引」的方案（称为 leftBound）
利用 leftBound 可知，找到「== x 的最右侧索引」问题可以转换为找到「>= x+1 的最左侧索引再 -1」即 leftBound(target+1)-1
| Code Block |
|---|
func searchRight(nums []int, target int) int {
// 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1
x := leftBound(nums, target + 1) - 1
// 注意此时 target+1 过小时，x = -1
if x == -1 || nums[x] != target {
return -1
}
return x
}
// 返回 >= target 的最小索引
func leftBound(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
}
}
return right
}
// 上面的 leftBound 是从之前的 searchLeft 中拆出来的 —— 利用 leftBound 重写 searchLeft 的话如下
func searchLeft(nums []int, target int) int {
x := leftBound(nums, target)
if x >= len(nums) || nums[x] != target {
return -1
}
return x
} |
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 完成 ：
| Code Block |
|---|
|
func searchRange(nums []int, target int) []int {
l := searchLeft(nums, target)
if l == -1 {
return []int{-1, -1}
}
r := searchRight(nums, target)
return []int{l, r}
}
func searchLeft(nums []int, target int) int {
x := leftBound(nums, target)
if x >= len(nums) || nums[x] != target {
return -1
}
return x
}
func searchRight(nums []int, target int) int {
// 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1
x := leftBound(nums, target + 1) - 1
// 注意此时 target+1 过小时，x = -1
if x == -1 || nums[x] != target {
return -1
}
return x
}
// 返回 >= target 的最小索引
func leftBound(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
}
}
return right
} |
LCCN LCR 172. 统计目标成绩的出现次数
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/
本题与上一题几乎一样（只有返回值不一样）
采用 rightBound 完成：
| Code Block |
|---|
|
func countTarget(scores []int, target int) int {
l := searchLeft(scores, target)
if l == -1 {
// score not exist
return 0
}
r := searchRight(scores, target)
return r-l+1
}
func searchLeft(nums []int, target int) int {
x := rightBound(nums, target-1) + 1
if x >= len(nums) || nums[x] != target {
return -1
}
return x
}
func searchRight(nums []int, target int) int {
x := rightBound(nums, target)
if x < 0 || nums[x] != target {
return -1
}
return x
}
// 返回 <= target 的最大索引
func rightBound(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] <= target {
left = mid + 1
} else{
right = mid
}
}
return left - 1
} |
LC.278 First Bad Version 第一个错误的版本
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
| Code Block |
|---|
|
/**
* 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+1
for l < r {
mid := l + (r - l) / 2
if isBadVersion(mid) {
// >= mid all bad
r = mid
} else {
l = mid + 1
}
}
return r
} |