一个几乎全民都会的算法——二分查找

为什么说二分查找是全民都会的算法？

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 main

import "fmt"

// 二分查找算法
func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (left + right) / 2
		if 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 := 8
	fmt.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 main

import "fmt"

// 二分查找算法
func binarySearchRecursive(arr []int, target int, left int, right int) int {
	if left > right {
		return -1
	}
	mid := left + (right-left)/2
	if 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 := 8
	left, right := 0, len(nums)-1
	fmt.Println(binarySearchRecursive(nums, target, left, right))
}

例程演示

用代码实现前文提到的猜价格游戏：

package main

import "fmt"

// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {
	if low > high {
		return -1
	}
	count++
	mid := low + (high-low)/2
	fmt.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 main

import "fmt"

// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {
	if low > high {
		return -1
	}
	count++
	mid := low + (high-low)/2
	fmt.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 main

import "fmt"

// 二分查找算法
func binarySearchRecursive(target int, low int, high int, count int) int {
	if low > high {
		return -1
	}
	count++
	mid := low + (high-low)/2
	fmt.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

给定一个按照升序排列的整数数组 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 <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

代码： 

package main
 
import "fmt"
 
func searchRange(nums []int, target int) []int {
	left, right := -1, -1
	// 查找左边界
	l, r := 0, len(nums)-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			left = mid
			r = 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)-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			right = mid
			l = 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

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 2^31 - 1

代码：  

package main
 
import (
	"fmt"
)
 
func mySqrt(x int) int {
	left, right := 0, x
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		guess := mid * mid
		if guess <= x {
			res = mid
			left = 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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [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]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(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.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

代码：  

package main

import "fmt"

func findMin(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if 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

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-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 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

代码：  

package main

import "fmt"

func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if 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

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

提示：

• 1 <= num <= 2^31 - 1

代码：

package main

import "fmt"

func isPerfectSquare(num int) bool {
	left, right := 1, num
	for left <= right {
		mid := left + (right - left) / 2
		square := mid * mid
		if 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

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 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 <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= m <= min(50, nums.length)

package main

import "fmt"

func splitArray(nums []int, m int) int {
	left, right := 0, 0
	for _, num := range nums {
		right += num
		if left < num {
			left = num
		}
	}
	for left <= right {
		mid := left + (right-left)/2
		if check(nums, m, mid) {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

func check(nums []int, m, target int) bool {
	sum, cnt := 0, 1
	for _, num := range nums {
		if sum+num <= target {
			sum += num
		} else {
			sum = num
			cnt++
			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

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例 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 <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• 对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

代码：

package main

import "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]+k
	return 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