算法-二分查找.md

算法-二分查找

给定一个由 n 个元素组成的排序数组 arr，编写一个函数来搜索 arr 中给定的元素。

一个简单的方法是进行线性搜索。线性搜索算法的时间复杂度为 O(n)。另一种方法是使用二分法查找。

二分查找

通过重复将搜索间隔减半来搜索已排序的数组。

如果搜索关键字的值小于间隔中间的值，则将间隔缩小到下半部分。否则，将其缩小到上半部分，反复检查，直到找到值或间隔为空。

Example

二分查找的思想是利用数组被排序的信息，并将时间复杂度降到 O(lgn)

在一次比较之后，我们基本上忽略了一半的元素：

1. 将 x 与中间元素进行比较
2. 如果 x 与中间元素匹配，则返回中间索引
3. 否则，如果 x 大于 mid 元素，则 x 只能位于 mid 元素之后的右半子数组中，所以我们会在右半部分反复执行逻辑
4. 否则，会在左半部分反复执行逻辑

可以看下二分查找的递归实现：

func binarySearch(arr []int, l, r, x int) (index int) {
	if r >= l {
		mid := l + (r-l)/2

		if arr[mid] == x {
			return mid
		}

		if arr[mid] > x {
			return binarySearch(arr, l, mid-1, x)
		}

		return binarySearch(arr, mid+1, r, x)
	}
	return -1
}

以下是二分查找的迭代实现：

func binarySearchIterative(arr []int, l, r, x int) int {
	for l <= r {
		mid := l + (r-l)/2

		if arr[mid] == x {
			return mid
		}

		if arr[mid] < x {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return -1
}