Go面试中如果这样写二分查找！
共 5591字，需浏览 12分钟
·
2021-07-04 13:05
前言
今天与大家分享一下
Go标准库sort.Search是如何实现二分查找的，为什么突然想到分享这个函数呢。起因是这周在刷leetcode的一道题时，需要使用到二分查找，最开始是自己实现了一版，后面就想Go语言标准库这么全，应该会有这个封装，果然被我找到了，顺便看了一下他是怎么实现的，感觉挺有意思的，就赶紧来分享一下。
什么是二分查找
以下来自百度百科：
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
总结一下，使用二分查找必须要符合两个要求：
必须采用顺序存储结构 必须按关键字大小有序排列
我们来举个例子，就很容易理解了，就拿我和我女朋友的聊天内容做个例子吧：
我家宝宝每次买一件新衣服，就会习惯性的问我一句，小松子，来猜一猜我这次花了多少钱？
小松子：50？
臭宝：你埋汰我呢？欠打！
小松子：500？
臭宝：你当我是富婆呢？能不能有点智商！
小松子：250？
臭宝：我感觉你在骂我，可我还没有证据。少啦，少啦！！！
小松子：哎呀，好难猜呀，290？
臭宝：啊！你这臭男人，就是在骂我！气死啦，气死啦！多啦，多啦！
小松子：难道是260？
臭宝：哎呦，挺厉害呀，竟然猜对了！
后面对话内容就省略啦.....
这里我只需要5次就成功猜出来了，这就是二分查找的思想，每一次猜测，我们都选取一段整数范围的中位数，根据条件帮我们逐步缩小范围，每一次都以让剩下的选择范围缩小一半，效率提高。
二分查找的时间复杂度
二分查找每次把搜索区域减少一半，时间复杂度为O(logn)。（n代表集合中元素的个数）。
空间复杂度为O(1)。
自己实现一个二分查找
二分算法的实现还是比较简单的，可以分两种方式实现：递归和非递归方式实现，示例代码如下：
非递归方式实现：
// 二分查找非递归实现
func binarySearch(target int64, nums []int64) int {
left := 0
right := len(nums) - 1
for left <= right {
mid := left + (right - left) / 2
if target == nums[mid] {
return mid
}
if target > nums[mid] {
left = mid + 1
continue
}
if target < nums[mid] {
right = mid - 1
continue
}
}
return -1
}
总体思路很简单，每次我们都选取一段整数范围的中位数，然后根据条件让剩下的选择范围缩小一半。这里有一个要注意的点就是我们在获取中位数时使用的写法是mid := left + (right - left) / 2，而不是mid = （left +right）/2的写法，这是因为后者有可能会造成位数的溢出，也就会导致结果出问题。
递归方式实现：
func Search(nums []int64, target int64) int {
return binarySearchRecursive(target, nums, 0, len(nums))
}
func binarySearchRecursive(target int64, nums []int64, left, right int) int {
if left > right {
return -1
}
mid := left + (right - left) / 2
if target == nums[mid] {
return mid
}
if nums[mid] < target {
return binarySearchRecursive(target, nums, mid+1, right)
}
if nums[mid] > target {
return binarySearchRecursive(target, nums, left, mid-1)
}
return -1
}
Go标准库是如何实现二分查找的？
我们先看一下标准库中的代码实现：
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
}
初一看，与我们上面的实现一点也不同呢，我们来分析一下。
入参n就是代表要查找序列的长度，入参f就是我们自定义的条件。这段代码很短，大概思路就是：
定义好这段序列的开始、结尾的位置 使用位移操作获取中位数，这样能更好的避免溢出 然后根据我们传入的条件判断是否符合条件，逐渐缩小范围
这段代码与我实现的不同在于，它并不是在用户传入的比较函数f返回true就结束查找，而是继续在当前[i, j)区间的前半段查找，并且，当f为false时，也不比较当前元素与要查找的元素的大小关系，而是直接在后半段查找。所以for循环退出的唯一条件就是i>=j，如果我们这样使用，就会出现问题：
func main() {
nums := []int64{1, 2, 3, 4, 5, 6, 7}
fmt.Println(sort.Search(len(nums), func(i int) bool{
return nums[i] == 1
}))
}
运行结果竟然是7，而不是1，如果我们把条件改成return nums[i] >=1，运行结果就对了。这是因为我们传入的条件并不是让用户确认目标条件，这里的思想是让我们逐步缩小范围，通过这个条件，我们每次都可以缩小范围，说的有点饶，就上面的代码举个例子。现在是一个升序数组，我们要找的数值是1，我们传入的条件是return nums[i]>=1，第一进入函数Search，我们获取中的中位数h是3，当前元素是大于目标数值的，所以我们只能在前半段查找，就是这样不断缩小范围，找到我们最终的那个数值，如果当前序列中没有我们要找的目标数值，那么就会返回我们可以插入的位置，也就是最后一位元素的坐标+1的位置。
这个逻辑说实话，我也是第一次接触，仔细思考了一下，这种实现还是有一些优点的：
使用移位操作，避免因为 i+j太大而造成的溢出如果我们查找序列中有多个元素相等时，且我们要找的元素就是这个时，我们总会找到下标最小的那个元素 如果我们没找到要找的目标元素时，返回的下标是我们可插入的位置，我们在进行数据插入时，依然可以保证数据的有序
注意：使用sort.Search时，入参条件是根据要查找的序列是升序序列还是降序序列来决定的，如果是升序序列，则传入的条件应该是>=目标元素值，如果是降序序列，则传入的条件应该是<=目标元素值
解析int(uint(i+j) >> 1)这段代码
这里我想单独解析一下这段代码，因为很少见，所以可以当作一个知识点记一下。这里使用到的是移位操作，通过向右移动一位，正好可以得到/2的结果。具体什么原因呢，我画了一个图，手工画的，看完你就懂了：
懂了吧，兄弟们！移位实现要比乘除发的效率高很多，我们在平常开发中可以使用这种方式来提升效率。
这里还有一个点就是使用uint数据类型，因为uint的数据范围是2^32即0到4294967295。使用uint可以避免因为i+j太大而造成的溢出。
总结
好啦，今天的文章到这里就结束了，最后我想说的是，没事大家可以专研一下Go标准库中的一些方法是怎样实现的，好的思想我们要借鉴过来。如果我们在面试中使用这种方式写出二分查找，那得到的offer的几率不就又增加了嘛～。
推荐阅读