前言
asongGosort.SearchleetcodeGo什么是二分查找
以下来自百度百科：
二分查找也称折半查找（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)
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) / 2mid = （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
}初一看，与我们上面的实现一点也不同呢，我们来分析一下。
nf- 定义好这段序列的开始、结尾的位置
- 使用位移操作获取中位数，这样能更好的避免溢出
- 然后根据我们传入的条件判断是否符合条件，逐渐缩小范围
ftrue[i, j)ffalsefori>=jfunc main() {
nums := []int64{1, 2, 3, 4, 5, 6, 7}
fmt.Println(sort.Search(len(nums), func(i int) bool{
return nums[i] == 1
}))
}71return nums[i] >=11return nums[i]>=1Searchh3这个逻辑说实话，我也是第一次接触，仔细思考了一下，这种实现还是有一些优点的：
i+jsort.Search>=目标元素值<=目标元素值int(uint(i+j) >> 1)/2
懂了吧，兄弟们！移位实现要比乘除发的效率高很多，我们在平常开发中可以使用这种方式来提升效率。
uintuint2^3204294967295uinti+j总结
Goofferasong创建了一个Golang学习交流群，欢迎各位大佬们踊跃入群，我们一起学习交流。入群方式：关注公众号获取。更多学习资料请到公众号领取。
推荐往期文章：