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]之间。

解题思路

这道题目的重点是题干中说：有序数组，同时题目还强调 数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当看到题目描述满足如上条件的时候，就要想一想是不是可以用二分法了。

二分查找虽然逻辑比较简单，但难点是它涉及到很多 边界条件：例如到底是 while(left < right) 还是 while(left <= right)，到底是 right = middle 呢，还是要 right = middle - 1 呢？

写二分法容易写乱，就是因为 对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是 循环不变量 规则。

区间的定义我选择左闭右闭即 [left, right]，第一反应是用递归来写二分法，使用递归算法并不一定是在性能上是最优的，但递归能简化代码形式。

我的思路：

设定左右指针 left、right
找出中间位置 middle，并判断该位置的值是否等于 target
若 nums[middle] == target，则返回 middle 下标
若 nums[middle] > target，则 right 指针移到 middle - 1 的位置
若 nums[middle] < target，则 left 指针移到 middle + 1 的位置
终止条件：找到了满足需求的 middle 或者左右指针不满足 left <= right 的边界条件

我的递归代码

java

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    return binarySearch(nums, left, right, target);
}

public int binarySearch(int[] nums, int left, int right, int target) {
    if (left > right) return -1;
    int middle = left + (right - left) / 2;
    if (nums[middle] == target) {
        return middle;
    } else if (nums[middle] < target) {
        return binarySearch(nums, middle + 1, right, target);
    } else if (nums[middle] > target) {
        return binarySearch(nums, left, middle - 1, target);
    }
}

时间复杂度：O(log n)

空间复杂度：O(log n)

递归算法的时间复杂度 = 递归的次数 * 每次递归中的操作次数

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

每次递归的空间复杂度可以看出主要就是参数里传入的这个 nums 数组，但需要注意的是在 C/C++/Java 中函数传递数组参数，不是整个数组拷贝一份传入函数而是传入的数组首元素地址。

也就是说每一层递归都是公用一块数组地址空间的，所以每次递归的空间复杂度是常数即：O(1)。

再来看递归的深度，二分查找的递归深度是 log n ，递归深度就是调用栈的长度，那么这段代码的空间复杂度为 1 * log n = O(log n)。

大家要注意自己所用的语言在传递函数参数的时，是拷贝整个数值还是拷贝地址，如果是拷贝整个数值那么该二分法的空间复杂度就是O(n log n)

计算 middle 时需要防止数值溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了因为 left 和 right 太大，导致直接相加数值溢出的情况。

递归改成循环

java

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    return binarySearch(nums, left, right, target);
}

public int binarySearch(int[] nums, int left, int right, int target) {
    int result = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            result = middle;
            break;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] > target)  {
            right = middle - 1;
        }
    }
    return result;
}

时间复杂度：O(log n)

空间复杂度：O(1)

总结

二分法需要注意搜索的区间和 while 的终止条件。

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。

使用递归算法并不一定是在性能上是最优的，但递归能简化代码层面的复杂程度。

递归算法的时间复杂度 = 递归的次数 * 每次递归中的操作次数

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

704.二分查找 ​

解题思路 ​

我的递归代码 ​

递归改成循环 ​

总结 ​

704.二分查找

解题思路

我的递归代码

递归改成循环

总结