Go 实现二分查找

二分查找（Binary Search）是一种用于在有序数组中查找特定元素的高效算法。它的基本思想是通过反复将有序数组分成两半，确定目标元素可能存在的范围，然后逐步缩小这个范围直到找到目标元素或确定目标元素不存在。二分查找效率非常高，在100万条数据中，只需查找20次左右

以下是二分查找的基本步骤：

1. 初始化： 定义最小的指针 low 和一个最大的指针 hight，初始时分别指向数组的起始和结束位置。

2. 循环条件： 当 low 小于等于 hight 时，继续执行以下步骤。

3. 计算中间位置： 计算中间位置 middleIndex ，可以使用 (low+ hight) / 2，但要注意溢出问题。更安全的方式是使用 low+ (hight - low) / 2。

4. 比较目标值： 将目标值与中间位置的元素进行比较。

   • 如果目标值等于中间位置的元素，则找到目标，返回中间位置。
   • 如果目标值小于中间位置的元素，则目标可能在左半部分，缩小范围为 (low, middleIndex -1)。
   • 如果目标值大于中间位置的元素，则目标可能在右半部分，缩小范围为 (middleIndex +1, hight)。

5. 循环结束： 如果循环结束时仍未找到目标元素，说明目标元素不存在于数组中，返回 -1。

以下是一个简单的二分查找的示例代码（假设数组 arr 是有序的）：

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

	}
	return 0
}

func main() {
	arr := []int{1, 2, 5, 8, 11, 13}
	a := binarySearch(arr, 13)
	fmt.Println(a)
}

这个算法的时间复杂度是 O(log n)，其中 n 是数组的长度。在有序数组中，二分查找是一种非常高效的查找算法。