这是算法记录的第17天，主要是对二分法的回顾与分析
对应leetcode题目为34.704.剑指I-53
二分法算是最基础的方法之一，它对长度为n的数组查找时间复杂度从O(n)降低到了O(logn)。二分查找的思路确实比较简单，但对于边界的把控却有一定难度，一不小心就搞错了，而且后面也有不少题可以用到二分法，所以这里单独一篇进行回顾与整理以加深印象。
不论如何首先要明确的是：只能对排序数组使用。
下面从三道题分析（实际就两道）
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
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
代码
直接先看代码
func searchInsert(nums []int, target int) int {
left := 0
//右边是开区间，取不到值
right := len(nums)
//终止条件是left=right
for left < right {
// 防止left+right太大导致溢出
mid := left + (right-left)>>1
if nums[mid] == target {
return mid
} else if nums[mid] < target {
//左闭，可以取到
left = mid + 1
} else if nums[mid] > target {
//右开，这个值取不到
right = mid
}
}
return -1
}
分析
代码细节在注释中，下面主要分析边界问题。
二分法首先要确定的是右边闭不闭，对应的是nums.len() - 1和nums.len()，这两种都行但不能搞混。
上面是基于不闭的情况实现的，也就是[left, right)。那么就应该始终记住右边取不到值，所以循环的条件应该是left < right，这样最后循环的终止条件是left = right。
而对于两边都闭的话，也就是[left, right]。右边的值是有效的，循环条件中left == right的情况是有效值，所以是<=，而循环的终止条件是left > right，实际上是left = right + 1。
综上，对于二分法类型的题目，需要明确三点：
- 右边界是开区间还是闭
- 循环条件那里是否取等
- 循环的终止条件是什么
这三点都是环环相扣的，前两点是二分成功的关键，最后一点则是实际完成题目要求的关键，下面一个题更体现出第三点的作用。
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 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]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
思路
这道题也就是二分法进行查找操作，理论时间复杂度是O（logn）
寻找左右边界问题也是二分法的常用场景，与基本的二分法不同，这里是找到目标值后不直接返回结果，而是缩小区间，继续查找是否存在索引更小/大的目标值。对于这道题进行两次二分法，分别找到左右边界值返回就行。
代码
func searchRange(nums []int, target int) (ans []int) {
if len(nums) == 0 {
return []int{-1, -1}
}
left, right := 0, len(nums)
if target < nums[left] || target > nums[right-1] {
return []int{-1, -1}
}
//先找左边界
for left < right {
mid := left + (right-left)>>1
if nums[mid] == target {
right = mid
} else if nums[mid] > target {
right = mid
} else if nums[mid] < target {
left = mid + 1
}
}
if nums[left] == target {
ans = append(ans, left)
} else {
ans = append(ans, -1)
}
left, right = 0, len(nums)
//再找右边界
for left < right {
mid := left + (right-left)>>1
if nums[mid] == target {
left = mid + 1
} else if nums[mid] > target {
right = mid
} else if nums[mid] < target {
left = mid + 1
}
}
if nums[right-1] == target {
ans = append(ans, right-1)
} else {
ans = append(ans, -1)
}
return ans
}
分析
综上，对于二分法类型的题目，需要明确三点：
- 右边界是开区间还是闭
- 循环条件那里是否取等
- 循环的终止条件是什么
对于前两点不再赘述，这一题第三点则是关键，下面分别对左、右两种情况的终止情况进行分析。
由于都是左闭右开的区间，所以循环条件是不需要取等的，所以第三点循环的终止条件就是相等的情况。
先找左边界。对于找到了目标值，我们应该向左边缩小搜索区间，所以右边界赋值为mid，注意此时右边界就是目标值，如果此时跳出循环，左右边界相等且都等于目标值。为了更直观地取左边界，所以后面就用的left来表示左边界（实则左右都可以，因为相等）。
再找右边界。对于找到了目标值，我们应该向右边缩小搜索区间，所以左边界收缩为mid+1。
为什么是+1呢？
因为是左闭的区间，要除去
mid这个值，所以下一次就从mid+1开始搜索那mid这个目标值不就丢失了吗？
你先别急。
当左边界收缩完了，进行下一次的循环判断时：
- 若
left < right仍成立，那么会在目标区间内继续找目标值，存在目标值就会拓宽目标值的右边界，不存在目标值那么就会通过二分不断地往左边缩，直到left = right； - 若
left = right在这一次循环判断一开始就成立，那么我们知道left = mid+1 = right，也就是目标值最大索引+1，所以后面需要-1，而因为找右边界所以是用right-1（实则左右都可以）
当然还有不存在目标值的情况，所以我们还需要对目标值与对应的索引值进行比较最后得到结果。
剑指I-53.在排序数组中查找数字
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
分析
这个直接做就是一个遍历，不过为了降低时间复杂度就用二分。
和上一个题完全一样，所以最开始说只有两道题，不过这道新增使用库函数，引入下面对源码的思考。
代码
下面将使用三个方式实现，两个二分搜索，一个遍历，可能是力扣测试用例原因，遍历的时间更快了…
- 标准实现-二分法
// 执行耗时:8 ms,击败了52.87% 的Go用户
// 内存消耗:3.8 MB,击败了59.93% 的Go用户
func search(nums []int, target int) int {
if len(nums) == 0 {
return 0
}
left, right := 0, len(nums)
l, r := 0, 0
if target < nums[left] || target > nums[right-1] {
return 0
}
//先找左边界
for left < right {
mid := left + (right-left)>>1
if nums[mid] == target {
right = mid
} else if nums[mid] > target {
right = mid
} else if nums[mid] < target {
left = mid + 1
}
}
if nums[left] == target {
l = left
} else {
l = 0
}
left, right = 0, len(nums)
//再找右边界
for left < right {
mid := left + (right-left)>>1
if nums[mid] == target {
left = mid + 1
} else if nums[mid] > target {
right = mid
} else if nums[mid] < target {
left = mid + 1
}
}
if nums[right-1] == target {
r = right - 1
} else {
r = -1
}
return r - l + 1
}
- 库函数实现
// 执行耗时:8 ms,击败了52.87% 的Go用户
// 内存消耗:3.8 MB,击败了36.89% 的Go用户
func search1(nums []int, target int) int {
leftmost := sort.SearchInts(nums, target)
if leftmost == len(nums) || nums[leftmost] != target {
return 0
}
rightmost := sort.SearchInts(nums, target+1) - 1
return rightmost - leftmost + 1
}
- 遍历
// 执行耗时:4 ms,击败了95.85% 的Go用户
// 内存消耗:3.8 MB,击败了36.89% 的Go用户
func search3(nums []int, target int) int {
ans := 0
for i := 0; i < len(nums); i++ {
if nums[i] == target {
ans++
}
}
return ans
}
Go怎么实现的？
看到上面用sort包直接搜索就看了下是如何实现的，正好也是二分法与自己写的比较一下有什么区别。
源码为了抽象出来给不同的类型使用是传入了个函数进行回调， 进行了wrappers处理，下面是一个整型的
func SearchInts(a []int, x int) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
二分具体实现
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
可以看到和官方的差不多，除了包装函数外就是在处理整型溢出不同：
h := int(uint(i+j) >> 1) 这行代码将无符号整数的平均值转换为有符号整数。它的好处是避免了对负数进行平均值运算的问题，因为对两个负数求和可能会导致溢出，而导致结果错误。
从语言层面来说，这种方式在 Golang 中使用较广，因为它可以避免对负数求和导致的溢出问题。
而对于计算整数区间的中间位置，两种方式都可以使用。在这种情况下，left + (right-left)>>1 的方式更为常见和易于理解。