「力扣」第 704 题：二分查找（简单）

发布日期: 2017-05-28

链接

给定一个 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
提示：

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

思路

根据看到的中间元素的数值，想清楚下一次搜索的区间是什么，进而设置 left 或者 right 的值。

方法一：在循环的过程中判断目标元素是否存在

这个版本的二分查找是教科书里经常介绍的写法。

在循环中做判断，每一轮通过目标元素与中间元素的大小将搜索区间分为 3 个部分；
有非递归写法和递归写法。
优点：语义非常清晰，不容易出错；

参考代码 1：

Java 代码：（循环写法）

public class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        // 在 [left, right] 区间里查找 target
        int left = 0;
        int right = len - 1;
        while (left <= right) {

            int mid = (left + right) >>> 1;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                // 下一轮搜索区间：[left, mid - 1]
                right = mid - 1;
            } else {
                // 此时：nums[mid] < target
                // 下一轮搜索区间：[mid + 1, right]
                left = mid + 1;
            }
        }
        // 走到这里，就可以判定输入数组里不存在目标元素，返回 -1
        return -1;
    }
}

Java 代码：（递归写法）

public class Solution {

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

    private static int binarySearch(int[] arr, int target, int left, int right) {
        // 先处理递归到底的情况
        if (left > right) {
            // 不能形成区间，返回 -1 表示没有找到
            return -1;
        }
        int mid = (left + right) >>> 1;
        if (target == arr[mid]) {
            // 找到了，就将目标元素的索引返回
            return mid;
        } else if (target < arr[mid]) {
            // 既然是有序数组，目标元素的值比中间元素还要小，就应该在中间元素的左边去找
            return binarySearch(arr, target, left, mid - 1);
        } else {
            // 既然是有序数组，目标元素的值比中间元素还要大，就应该在中间元素的右边去找
            return binarySearch(arr, target, mid + 1, right);
        }
    }
}

复杂度分析：

时间复杂度：$O(\log N)$，这里 $N$ 是数组的元素个数，每次排除当前候选区间一半以上的元素，因此是对数级别的时间复杂度。
空间复杂度：$O(1)$，只使用了常数个的临时变量。

方法二：在循环结束以后判断目标元素是否存在

特点：在循环结束以后判断目标元素是否存在。在循环中，分支只有两个判断更少。

缺点：如果这个模板写法掌握得不好，容易出错。

Java 代码：

public class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {

            int mid = (left + right) >>> 1;

            if (nums[mid] < target) {
                // 下一轮搜索区间是：[mid + 1, right]
                left = mid + 1;
            } else {
                // 此时 nums[mid] >= target，
                // mid 的右边一定不存在 target，下一轮搜索区间是：[left, mid]
                right = mid;
            }
        }
        // 不要忘了单独做判断
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
}

Java 代码：

public class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;

        int left = 0;
        int right = len - 1;

        while (left < right) {
            // 注意：根据分支逻辑，需要在取中间数的时候，向上取整
            int mid = (left + right + 1) >>> 1;

            if (nums[mid] > target) {
                // 下一轮搜索区间是：[left, mid - 1]
                right = mid - 1;
            } else {
                // 此时 nums[mid] <= target
                // mid 的左边一定不等于目标元素
                // 下一轮搜索区间是：[mid, right]
                left = mid;
            }
        }
        // 不要忘了单独做判断
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
}