关于算法:Leetcode-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

解题思路

二分查找根本框架如下：

int binarySolution(int[] nums, int target) {
    int left = 0, right = ...;
    while (...) {int mid = left + (right - left) / 2;
        if (nums[mid] == target) {...} else if (nums[mid] < target) {left = ...;} else if (nums[mid] > target) {right = ...;}
    }
    return ...;
}

剖析二分查找的一个技巧是：不要呈现 else，而是把所有状况用 else if 写分明，这样能够分明地展示所有细节。

其中 ... 标记的局部，就是可能呈现细节问题的中央，当你见到一个二分查找的代码时，首先留神这几个中央。

另外申明一下，计算 mid 时须要避免溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的后果雷同，然而无效避免了 left 和 right 太大间接相加导致溢出。

对于本题的题解如下：

class Solution {public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 留神
        // 留神
        while (left <= right) {int mid = left + (right - left) / 2;
            if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1; // 留神} else if (nums[mid] > target) {right = mid - 1; // 留神}
        }
        return -1;
    }
}

这里探讨一下其中的几个细节。

1、为什么 while 循环的条件中是 <=，而不是 <？

答：因为初始化 right 的赋值是 nums.length - 1，即最初一个元素的索引，而不是 nums.length。

因为咱们须要对所有的元素进行搜寻，应用 <= 搜寻的是两端都闭区间 [left, right]，如果应用 < 则相当于左闭右开区间 [left, right)。

如果应用 <，而后 right 初始赋值改为 nums.length，也可实现 [left, right] 范畴的搜寻，但会漏掉最初一个元素，上面会讲

此外还要留神下完结搜寻的条件。当找到目标值的时候能够终止：nums[mid] == target。如果没找到，就须要 while 循环终止，而后返回 -1。那 while 循环什么时候应该终止？ 搜寻区间为空的时候应该终止。

while(left <= right) 的终止条件是 left == right + 1，写成区间的模式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]。

while(left < right) 的终止条件是 left == right，写成区间的模式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜寻，如果这时候间接返回 -1 就是谬误的。

如果要用 while(left < right) 也是能够的，咱们曾经晓得了出错的起因，就打个补丁好了：

class Solution {public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {int mid = left + (right - left) / 2;
            if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;}
        }
        // 对漏掉的元素进行判断
        return nums[left] == target ? left : -1;
    }
}

2、为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid

方才明确了「搜寻区间」这个概念，而且本算法的搜寻区间是两端都闭的，即 [left, right]。那么当咱们发现索引 mid 不是要找的 target 时，下一步应该去搜寻哪里呢？

当然是去搜寻 [left, mid-1] 或者 [mid+1, right] 对不对？ 因为 mid 曾经搜寻过，应该从搜寻区间中去除。

3、此算法有什么缺点？

比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。然而如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无奈解决的。

这样的需要很常见， 你兴许会说，找到一个 target，而后向左或向右线性搜寻不行吗？能够，然而不好，因为这样难以保障二分查找对数级的复杂度了。

总结

• 不要应用 else，而是把所有状况用 else if 写分明
• 计算 mid 时须要避免溢出，应用 left + (right - left) / 2 先减后加这样的写法
• while 循环的条件 <= 对应 right 初始值为 nums.length - 1，终止条件是 left == right + 1，例如 [3, 2]
• 如果 while 循环的条件 <，须要把 right 初始值改为 nums.length，此时终止条件是 left == right，例如 [2, 2]，这样会漏掉最初一个区间的元素，须要独自判断下
• 当 mid 不是要找的 target 时，下一步应该搜寻 [left, mid-1] 或者 [mid+1, right]，对应 left = mid + 1 或者 right = mid - 1
• 二分查找时间复杂度 O(logn)