704.二分查找

一、问题描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

• 你可以假设 nums 中的所有元素是不重复的。
• n 将在 [1, 10000]之间。
• nums 的每个元素都将在 [-9999, 9999]之间。

二、方案一：标准二分查找

1、思路

• 初始化左右指针 left 和 right。
• 当 left <= right 时，执行循环：
  • 计算中间位置 mid = (left + right) / 2。
  • 如果 nums[mid] == target，返回 mid。
  • 如果 nums[mid] < target，设置 left = mid + 1。
  • 如果 nums[mid] > target，设置 right = mid - 1。
• 如果循环结束还没有找到，返回 -1。

2、代码实现

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

3、复杂度分析

• 时间复杂度：O(log n)，其中 n 是数组的长度。二分查找的时间复杂度是对数级别的。
• 空间复杂度：O(1)，只需要常数级别的额外空间。

三、方案二：递归二分查找

1、思路

• 递归地将数组分为两半，检查中间元素是否为目标值。
• 如果中间元素是目标值，返回其索引。
• 如果中间元素小于目标值，递归地在右半部分查找。
• 如果中间元素大于目标值，递归地在左半部分查找。
• 如果没有找到，返回 -1。

2、代码实现

func search(nums []int, target int) int {
    return searchHelper(nums, target, 0, len(nums)-1)
}
func searchHelper(nums []int, target int, left int, right int) int {
    if left > right {
        return -1
    }
    mid := (left + right) / 2
    if nums[mid] == target {
        return mid
    } else if nums[mid] < target {
        return searchHelper(nums, target, mid+1, right)
    } else {
        return searchHelper(nums, target, left, mid-1)
    }
}

3、复杂度分析

• 时间复杂度：O(log n)，其中 n 是数组的长度。递归二分查找的时间复杂度与迭代版本相同。
• 空间复杂度：O(log n)，由于递归调用会使用栈空间，其空间复杂度是递归深度的对数级别。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
迭代	O(log n)	O(1)	空间效率高	无
递归	O(log n)	O(log n)	代码简洁	需要更多空间

迭代和递归二分查找在时间复杂度上相同，都是 O(log n)。迭代版本在空间上更优，因为它只需要常数级别的额外空间。递归版本代码更简洁，但需要额外的栈空间，其空间复杂度是递归深度的对数级别。