Binary Search

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

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

普遍算法

只采取左闭右开方式。

func BinarySearch(arr []int, target int) (int, int) {
	lo, hi := 0, len(arr)
	for lo < hi {
		mid := lo + ((hi - lo) >> 2)
		if arr[mid] > target {
			hi = mid
		} else if arr[mid] < target {
			lo = mid + 1
		} else {
			return mid, -1
		}
	}
	return -1, lo
}

变体

元素可重复数组中找到第一个出现的

最后返回 left 或 right 都无所谓，因为退出循环一定意味着两者相等。

func BinarySearchFirst(arr []int, target int) (int, int) {
	lo, hi := 0, len(arr)
	for lo < hi {
		mid := lo + ((hi - lo) >> 2)
		if arr[mid] >= target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	if lo < len(arr) && arr[lo] == target {
		return lo, -1
	}
	return -1, lo
}

元素可重复数组中找到最后一个出现的

最后返回 left 或 right 都无所谓，因为退出循环一定意味着两者相等。

func BinarySearchLast(arr []int, target int) (int, int) {
	lo, hi := 0, len(arr)
	for lo < hi {
		mid := lo + ((hi - lo) >> 2)
		if arr[mid] > target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	if lo > 0 && arr[lo-1] == target {
		return lo - 1, -1
	}
	return -1, lo
}

局限

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