Binary Search

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

• 时间复杂度 $O(\log n)$
• 空间复杂度 $O(1)$

区间表示方法

[low, high] 左闭右闭

由于 low、high 左右边界都是可达的，缩小的操作区间也是对称的，因此更推荐使用本方法，更不容易出错。但是 high 可能为负数（-1）。

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
}

局限

• 仅适用于有序数据
  • 若输入数据无序，排序通常时间复杂度为 $O(n\log n)$ ，比线性查找、二分查找都高
• 二分查找只适用于数组
  • 需要非连续地访问元素，不适用于链表
• 小数量下线性查找性能更好