介绍

二分查找（Binary Search）是一种高效的查找算法，用于在有序数组中查找特定元素的位置。二分查找的前提是数组必须是有序的，否则无法保证正确性。

算法步骤如下：

1. 初始化左右指针，左指针为数组的起始位置，右指针为数组的结束位置。
2. 当左指针小于等于右指针时，执行以下步骤：
3. 计算中间元素的索引，可以使用 (左指针 + 右指针) / 2 或者 左指针 + (右指针 – 左指针) / 2 来避免整数溢出问题。
4. 如果中间元素等于目标元素，返回中间元素的索引。
5. 如果中间元素大于目标元素，说明目标元素可能在左侧，将右指针更新为中间元素的前一个位置。
6. 如果中间元素小于目标元素，说明目标元素可能在右侧，将左指针更新为中间元素的后一个位置。
7. 如果循环结束时仍未找到目标元素，表示目标元素不存在于数组中，返回一个表示未找到的特定值（如 -1）。

代码示例

package main

import "fmt"

// 迭代
func binarySearch1(arr *[]int, target int, left, right int) int {
    for left < right {
    //在arr[left...right]中查找target
        //mid := (left + right) / 2
        //注意：这里容易产生bug（r+l溢出int最大值）,改写成如下方式
        mid := left + (right-left)/2
        if (*arr)[mid] == target {
            return mid
        } else if (*arr)[mid] > target {
        //在arr[left...middleIndex - 1]中查找target
            right = mid - 1
        } else {
        //在arr[middleIndex + 1...right]中查找target
            left = mid + 1
        }
    }
    fmt.Println("没找到")
    return -1
}

// 递归
func binarySearch2(arr *[]int, target int, left, right int) int {
    if left > right {
        fmt.Println("没找到")
        return -1
    }
    //mid := (left + right) / 2
    mid := left + (right-left)/2
    if (*arr)[mid] == target {
        return mid
    } else if (*arr)[mid] > target {
        return binarySearch2(arr, target, left, mid-1)
    } else {
        return binarySearch2(arr, target, mid+1, right)
    }
}

func main() {
    arr := []int{1, 3, 5, 7, 9}
    target1 := binarySearch1(&arr, 5, 0, len(arr)-1)
    target2 := binarySearch2(&arr, 5, 0, len(arr)-1)
    fmt.Println("找到了！下标为：", target1)
    fmt.Println("找到了！下标为：", target2)
}

复杂度

时间复杂度：

• 最坏情况下，目标元素不在数组中，二分查找需要执行的操作次数是 log₂(n)（以 2 为底的对数），其中 n 是数组的长度。每次迭代或递归都将搜索范围缩小为原来的一半，直到搜索范围为空。因此，时间复杂度为 O(log n)。
• 最好情况下，如果目标元素恰好是数组的中间元素，那么时间复杂度为 O(1)，即常数时间。这是因为只需一次比较就能找到目标元素。

每次迭代或递归都将搜索范围缩小一半，所以时间复杂度都是O(logN)，递归法的性能比迭代法的略差。

空间复杂度：

• 二分查找的空间复杂度为 O(1)，即常数空间。算法只需要使用几个变量来存储左右指针和中间索引，不随数组规模的增长而增加额外的空间占用。