二分查找

查找与遍历

说明

在有序数组中逐步排除一半候选；时间 O(log n)。

分析

维护一个可能包含目标值的半开区间 [l,r)，根据中点与目标的比较缩小一侧。循环结束后还需检查候选下标是否真的匹配。

图解推演

以有序数组 [1,3,5,7] 查找 5，半开区间初始 [0,4)，mid=2 的值已经不小于目标，令 r=2；下一次 mid=1 的值 3 太小，令 l=2，区间收敛到下标 2。最后检查 a[2]=5 才返回。该实现先求下界，所以重复值返回最左匹配；下界可能等于数组长度，必须先检查越界。

查看图表代码

适用前提与边界

前提是输入按相同规则排序；否则二分的排除逻辑不成立。

示例输入与调用

fmt.Println(BinarySearch([]int{1, 3, 5, 7}, 5))

运行输出

2

完整 Go 示例

package main

import "fmt"

func BinarySearch(a []int, target int) int {
	l, r := 0, len(a)
	for l < r {
		m := l + (r-l)/2
		if a[m] < target {
			l = m + 1
		} else {
			r = m
		}
	}
	if l < len(a) && a[l] == target {
		return l
	}
	return -1
}

func main() {
	fmt.Println(BinarySearch([]int{1, 3, 5, 7}, 5))
}