二分查找
二分查找常用来在排序数组中查找一个数的位置或者是一个数的边界。但是二分查找受到区间的影响很大。并且细节繁多，很容易就会产生偏差。二分查找不出错的关键就是先把所有的情况分支都完整的写出来，暂时不考虑分支合并的情况。总的来说只有三种分支情况那就是等于目标值、大于目标值以及小于目标值，基于这三种情况对边界进行修改。所以二分查找的基础框架如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func binarySearch(nums []int, target int) {
l, h := 0, len(num) or len(nums)-1
for l<h or l<=h {
mid := l + (h-l)/2
if nums[mid] == target {
//TODO
} else if nums[mid] < target {
//TODO l = ...
} else if nums[mid] > target {
//TODO h = ...
}
}
//TODO return ...
}
|
基本的二分搜搜
基本的二分搜索就是查找一个数据的位置，或者是判断这个数在不在数组中。一般二分搜索的关键是在于区间的改变，一般有两种方式，左闭右开或者是两端均闭合
左闭右开
左闭右开的意思就是左边的元素在此次搜索中可以访问到，右边的元素不可访问，所以区间[i,i)是没有意义的，不存在这种空间，所以循环条件为 $l<h$。并且为了保正每次修改区间之后仍未左闭右开，则$h$的每次改变应为$h = mid$。
完整代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func binarySearch(nums []int, target int) int {
// 我们遵循找下界的方式 即每次的区间改为左闭右开
// 所有的区间调整均要遵循左闭右开的原则
l, h := 0, len(nums)
for l < h {
mid := l + (h-l)/2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
l = mid + 1
} else if nums[mid] > target {
h = mid
}
}
return -1
}
|
双端闭合
双端闭合即两端元素均可访问，在这种情况下[i,i]是有意义的。所以循环条件为$l<=h$.而$h$的每次修改条件为$h=mid-1$.完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func binarySearch(nums []int, target int) int {
// 如果使用两边全部闭合的区间 则对应需要修改循环的结束条件以及每次区间修改
// 包括区间的起始也要保证是两边闭合即均可访问到
l, h := 0, len(nums)-1
// 两边闭合的情况下会出现 l==h的情况
for l <= h {
mid := l + (h-l)/2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
l = mid + 1
} else if nums[mid] > target {
//要保证两边均都要闭合
h = mid - 1
}
}
return -1
}
|
寻找左边界
更多情况下，二分搜索都是应用在搜索不是固定的目标问题上，最常见的一种是搜索边界问题，左边界或者是右边界。
左边界
我们是为了返回左边界的位置，所以等于目标值的时候缩小区间大小，并且缩小的右边界。其他情况不变，最后返回右边界和左边界都一样，因为循环截止条件就是$l==h$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
func searchLeft(nums []int, target int) int {
// 寻找左侧边界问题
// 应该使用左闭右开的区间大小
l, h := 0, len(nums)
for l < h {
// 只有这样最后可以精确的返回左边界
// 因为不是为了寻找确定的值的位置
// 所以等于的情况并不会进行返回 也是修改区间
// 可以看到 相等的情况和大于的情况是相同的处理，所以可以进行合并
mid := l + (h-l)/2
if nums[mid] == target {
// 我们是寻找左边界，所以需要修改h
// 又因为是左闭右开
h = mid
} else if nums[mid] < target {
//TODO l = ...
l = mid + 1
} else if nums[mid] > target {
//TODO h = .
h = mid
}
}
// 这里也可以返回h
return l
}
|
右边界
右边界和左边界类似，只是在等于的时候修改的的是$l$索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func searchRight(nums []int, target int) int {
l, h := 0, len(nums)
for l < h {
mid := l + (h-l)/2
if nums[mid] == target {
h = mid + 1
} else if nums[mid] < target {
//TODO l = ...
l = mid + 1
} else if nums[mid] > target {
//TODO h = .
h = mid
}
}
// 这里也可以返回h
return l - 1
}
|