Search CTRL + K

Binary Search

二分查找(binary search) 是基于分治策略的搜索算法,它利用数据有序性,每次搜索减少一半搜索范围。

区间表示方法

[low, high] 左闭右闭

由于 lowhigh 左右边界都是可达的,缩小的操作区间也是对称的,因此更推荐使用本方法,更不容易出错。

func binarySearch(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] < target {
			low = mid + 1
		} else if nums[mid] > target {
			high = mid - 1
		} else {
			return mid
		}
	}
	return -1
}

[low, high) 左闭右开

func binarySearch(nums []int, target int) int {
	low, high := 0, len(nums)
	for low < high {
		mid := low + (high-low)/2
		if nums[mid] < target {
			low = mid + 1
		} else if nums[mid] > target {
			high = mid
		} else {
			return mid
		}
	}
	return -1
}

局限