20年前央视2套有一档叫《幸运52》的综艺节目，其中一个环节叫《幸运超市》，每一期已故著名主持人咏哥都会给佳宾们出示几个商品，凡是佳宾猜中价格的，就能获赠这件商品。这档节目红极一时，被很多地方卫视节目复制抄袭。
比如，上面这段视频(gif图)的配音这样的：
佳宾报价：主持人说高或低
1800：高了
1500：低了
1600：低了
1700：高了
1680：高了
1660：低了
1670：正确！
上面这个猜价格过程，首先佳宾预估到这件的商品价格区间是1500到1800之间，然后根据主持人说高还是低进行调节报价高低，直到猜中价格。
是不是很简单！ 其实这一个猜价格过程就是二分查找算法。由于2000年前后的手机还没有多媒体化，这档节目收视率极高，所以这种猜价格的方法那时候几乎全民皆会，只是没命名它叫二分查找而已。
二分查找
也被称为折半查找，它的基本思想是：对于一个有序数组，每次查找中间位置的元素，如果该元素等于目标元素，则返回该元素的位置；如果该元素大于目标元素，则在数组的左半部分继续查找；如果该元素小于目标元素，则在数组的右半部分继续查找。重复以上过程，直到找到目标元素或者数组中不存在目标元素为止。
二分查找时间复杂度为O(log n)，是一种非常高效的查找算法。
基本过程
1.首先，将数组按照升序或者降序排列。
2.然后，确定数组的中间元素。
3.接着，将目标值与中间元素进行比较。
3-1.如果目标值等于中间元素，则查找成功，返回中间元素的位置。
3-2.如果目标值小于中间元素，则在左侧子数组中继续查找。
3-3.如果目标值大于中间元素，则在右侧子数组中继续查找。
重复执行步骤，直到查找成功或者确定目标元素不存在。
算法实现
给定一个有序数组和一个目标元素，求该元素在数组中的位置，如果数组中不存在该元素，则返回-1。例如，给定数组[1, 2, 3, 6, 8, 9, 10]和目标元素8，则返回3。
用Golang语言实现的代码如下：
package mainimport "fmt"// 二分查找算法
func binarySearch(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := (left + right) / 2if nums[mid] == target {return mid} else if nums[mid] > target {right = mid - 1} else {left = mid + 1}}return -1
}func main() {nums := []int{1, 2, 3, 6, 8, 9, 10}target := 8fmt.Println(binarySearch(nums, target))
}运行结果： 4，表示数组的第5个元素是8.
在本例中，我们定义了一个名为binarySearch的函数，该函数接受两个参数：
nums：有序数组， target：目标元素
在函数中，首先定义两个指针left和right，分别指向数组的左边界和右边界。然后使用一个循环，不断查找中间位置的元素，直到找到目标元素或者数组中不存在目标元素为止。在每次循环中，首先计算中间位置的索引mid，如果中间位置的元素等于目标元素，则返回中间位置的索引；如果中间位置的元素大于目标元素，则在数组的左半部分继续查找，将右边界指向中间位置的左侧；如果中间位置的元素小于目标元素，则在数组的右半部分继续查找，将左边界指向中间位置的右侧。重复以上过程，直到找到目标元素或者数组中不存在目标元素为止。
二分查找算法虽然简单，但是实现起来需要注意几个问题：
如何计算中间位置：在二分查找算法中，需要计算中间位置的索引，通常可以使用left和right指针来计算，即mid := (left + right) / 2，也有用右移运算的：(left + right) >> 1。
特别是当right接近最大整数Int_Max时，避免left,right相加后溢出，尽可能用：
mid := left + (right - left) / 2 或者 mid := left + (right - left) >> 1
递归法
递归法更好地展示了二分查找的过程：
package mainimport "fmt"// 二分查找算法
func binarySearchRecursive(arr []int, target int, left int, right int) int {if left > right {return -1}mid := left + (right-left)/2if arr[mid] == target { //“正确”return mid} else if target < arr[mid] { //“高了”return binarySearchRecursive(arr, target, left, mid-1)} else { //“低了”return binarySearchRecursive(arr, target, mid+1, right)}
}func main() {nums := []int{1, 2, 3, 6, 8, 9, 10}target := 8left, right := 0, len(nums)-1fmt.Println(binarySearchRecursive(nums, target, left, right))
}
例程演示
用代码实现前文提到的猜价格游戏：
package mainimport "fmt"// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {if low > high {return -1}count++mid := low + (high-low)/2fmt.Printf("第%v次报价:%v ", count, mid)if mid == target {fmt.Println("正确！")return mid} else if target < mid {fmt.Println("高了")return binarySearchRecursive(target, low, mid-1, count)} else {fmt.Println("低了")return binarySearchRecursive(target, mid+1, high, count)}
}func main() {target := 1670 //商品正确价格为1670元low, high := 1500, 1800 //预估商品价格区间binarySearchRecursive(target, low, high, 0)
}
运行结果：
第1次报价:1650 低了
第2次报价:1725 高了
第3次报价:1687 高了
第4次报价:1668 低了
第5次报价:1677 高了
第6次报价:1672 高了
第7次报价:1670 正确！
加上预估区间的2次，共9次猜出正确价格。为什么比人猜多了，因为人猜时默认价格是10的倍数，是没有个位数的。修改代码，也用mid+10 和 mid-10试试：
package mainimport "fmt"// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {if low > high {return -1}count++mid := low + (high-low)/2fmt.Printf("第%v次报价:%v ", count, mid)if mid == target {fmt.Println("正确！")return mid} else if target < mid {fmt.Println("高了")return binarySearchRecursive(target, low, mid-10, count)} else {fmt.Println("低了")return binarySearchRecursive(target, mid+10, high, count)}
}func main() {target := 1670 //商品正确价格为1670元low, high := 1500, 1800 //预估商品价格区间binarySearchRecursive(target, low, high, 0)
}
运行结果：
第1次报价:1650 低了
第2次报价:1730 高了
第3次报价:1690 高了
第4次报价:1670 正确！
虽然这个例子是猜中了，但对区间变动不是mid±1的还是谨慎使用，很可能会错失目标的。
盲猜：
如果不知道是什么商品，也就是估不准价格，比如我们指定是100000以内价格区间，看要猜多少次？
package mainimport "fmt"// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {if low > high {return -1}count++mid := low + (high-low)/2fmt.Printf("第%v次报价:%v ", count, mid)if mid == target {fmt.Println("正确！")return mid} else if target < mid {fmt.Println("高了")return binarySearchRecursive(target, low, mid-1, count)} else {fmt.Println("低了")return binarySearchRecursive(target, mid+1, high, count)}
}func main() {target := 1670 //商品正确价格为1670元low, high := 0, 100000 //预估商品价格区间binarySearchRecursive(target, low, high, 0)
}
运行结果：
第1次报价:50000 高了
第2次报价:24999 高了
第3次报价:12499 高了
第4次报价:6249 高了
第5次报价:3124 高了
第6次报价:1561 低了
第7次报价:2342 高了
第8次报价:1951 高了
第9次报价:1756 高了
第10次报价:1658 低了
第11次报价:1707 高了
第12次报价:1682 高了
第13次报价:1670 正确！
这个次数不高于log2(100000) ≈ 16.61，所以二分查找的时间复杂度为 O(log n)。
力扣实战
查找元素的首末位置
Find-first-and-last-position-of-element-in-sorted-array
numstargettarget[-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 <= 10^5-10^9 <= nums[i] <= 10^9nums-10^9 <= target <= 10^9代码：
package mainimport "fmt"func searchRange(nums []int, target int) []int {left, right := -1, -1// 查找左边界l, r := 0, len(nums)-1for l <= r {mid := (l + r) / 2if nums[mid] == target {left = midr = mid - 1} else if nums[mid] > target {r = mid - 1} else {l = mid + 1}}// 如果左边界没找到，直接返回if left == -1 {return []int{-1, -1}}// 查找右边界l, r = 0, len(nums)-1for l <= r {mid := (l + r) / 2if nums[mid] == target {right = midl = mid + 1} else if nums[mid] > target {r = mid - 1} else {l = mid + 1}}return []int{left, right}
}func main() {nums := []int{5, 7, 7, 8, 8, 10}fmt.Println(searchRange(nums, 8))fmt.Println(searchRange(nums, 6))nums = []int{}fmt.Println(searchRange(nums, 0))}x 的平方根 Sqrt x
xx由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
pow(x, 0.5)x ** 0.5示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1代码：
package mainimport ("fmt"
)func mySqrt(x int) int {left, right := 0, xres := -1for left <= right {mid := left + (right-left)/2guess := mid * midif guess <= x {res = midleft = mid + 1} else {right = mid - 1}}return res
}func main() {fmt.Println(mySqrt(4))fmt.Println(mySqrt(8))fmt.Println(mySqrt(122))
}寻找旋转排序数组中的最小值
Find-minimum-in-rotated-sorted-array
n1nnums = [0,1,2,4,5,6,7]4[4,5,6,7,0,1,2]7[0,1,2,4,5,6,7][a[0], a[1], a[2], ..., a[n-1]][a[n-1], a[0], a[1], a[2], ..., a[n-2]]numsO(log n)示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000numsnums1n代码：
package mainimport "fmt"func findMin(nums []int) int {left, right := 0, len(nums)-1for left < right {mid := left + (right-left)/2if nums[mid] > nums[right] {left = mid + 1} else {right = mid}}return nums[left]
}func main() {nums := []int{3, 4, 5, 1, 2}fmt.Println(findMin(nums))nums = []int{4, 5, 6, 7, 0, 1, 2}fmt.Println(findMin(nums))nums = []int{11, 13, 15, 17}fmt.Println(findMin(nums))
}
寻找峰值
Find Peak Element
峰值元素是指其值严格大于左右相邻值的元素。
numsnums[-1] = nums[n] = -∞O(log n)示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1inums[i] != nums[i + 1]代码：
package mainimport "fmt"func findPeakElement(nums []int) int {left, right := 0, len(nums)-1for left < right {mid := left + (right-left)/2if nums[mid] > nums[mid+1] {right = mid} else {left = mid + 1}}return left
}func main() {nums := []int{1, 2, 3, 1}fmt.Println(findPeakElement(nums))nums = []int{1, 2, 1, 3, 5, 6, 4}fmt.Println(findPeakElement(nums))
}
有效的完全平方数
Valid Perfect Square
numnumtruefalsesqrt示例 1：
输入：num = 16 输出：true
示例 2：
输入：num = 14 输出：false
提示：
1 <= num <= 2^31 - 1代码：package mainimport "fmt"func isPerfectSquare(num int) bool {left, right := 1, numfor left <= right {mid := left + (right - left) / 2square := mid * midif square == num {return true} else if square < num {left = mid + 1} else {right = mid - 1}}return false
}func main() {fmt.Println(isPerfectSquare(16))fmt.Println(isPerfectSquare(14))
}
分割数组的最大值
Split-array-largest-sum
numsmmm示例 1：
输入：nums = [7,2,5,10,8], m = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2 输出：9
示例 3：
输入：nums = [1,4,4], m = 3 输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= m <= min(50, nums.length)package mainimport "fmt"func splitArray(nums []int, m int) int {left, right := 0, 0for _, num := range nums {right += numif left < num {left = num}}for left <= right {mid := left + (right-left)/2if check(nums, m, mid) {right = mid - 1} else {left = mid + 1}}return left
}func check(nums []int, m, target int) bool {sum, cnt := 0, 1for _, num := range nums {if sum+num <= target {sum += num} else {sum = numcnt++if cnt > m {return false}}}return true
}func main() {nums := []int{7, 2, 5, 10, 8}fmt.Println(splitArray(nums, 2))nums = []int{1, 2, 3, 4, 5}fmt.Println(splitArray(nums, 2))nums = []int{1, 4, 4}fmt.Println(splitArray(nums, 3))}
第 k 个缺失的正整数
kth-missing-positive-number
arrkk示例 1：
输入：arr = [2,3,4,7,11], k = 5 输出：9 解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
示例 2：
输入：arr = [1,2,3,4], k = 2 输出：6 解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。
提示：
1 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 10001 <= i < j <= arr.lengthijarr[i] < arr[j]代码：
package mainimport "fmt"func findKthPositive(arr []int, k int) int {left, right := 0, len(arr)for left < right {mid := left + (right-left)/2// 计算当前位置缺失的数字个数count := arr[mid] - mid - 1// 如果缺失的数字个数小于k，说明第k个缺失的数字在右半部分if count < k {left = mid + 1} else {right = mid}}// 缺失的数字个数为k时，需要返回arr[left]-1// 因为arr[left]之前的数字都不缺失，所以缺失的第k个数字就是arr[left]+kreturn left + k
}func main() {nums := []int{2, 3, 4, 7, 11}fmt.Println(findKthPositive(nums, 5))nums = []int{1, 2, 3, 4}fmt.Println(findKthPositive(nums, 2))
}
还有很多适用十分查找的题目，不一一列举了。
总结
本文介绍了二分查找算法的原理、实现方法和用 Golang 实现的例程。二分查找算法是一种高效的查找算法，适用于有序数列中的查找问题。它的时间复杂度为 O(log n)，相比于线性查找的 O(n)，效率更高。在实际应用中，我们可以根据具体情况选择递归或循环实现二分查找算法，以提高算法的效率。
最后，请记牢二分查找标志性的语句：
mid := left + (right-left)/2