【刷题日记】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
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

二、解题

最基础的二分查找题目，二分就是说每次可以过滤掉一半的数据，适用于有序数组的查找。可以通过递归的方法来分别对左右数组区间进行搜索。要注意的是这里需要我们返回在原数组的下标，所以我们不能对数组做截断。

核心的点就是取中值，然后根据目标值的表现，继续到对应子区间做二分查找，是一个递归的过程。这里开始提交不通过， 因为描述数组下标的指针可能发生越界， 就补充了一些边界判断。最终是可以AC的：

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

    public int binarySearch(int[] n, int target, int startp, int endp) {

        if(startp < 0 || endp < 0 ||
            startp >= n.length || endp >= n.length ||
            (startp == endp && n[endp] != target)) {
            return -1;
        }

        int mid = (startp + endp) / 2;

        if(target < n[mid]) {
            return binarySearch(n, target, startp, mid - 1);
        } else if(target > n[mid]) { 
            return binarySearch(n, target, mid + 1, endp);
        } else {
            return mid;
        }
    } 
}

回顾以前的学习，我们知道JDK中已经有数组的二分查找实现。如Arrays.binarySearch，会先对输入参数做越界检查，后直接执行二分查找：

	public static int binarySearch(long[] a, int fromIndex, int toIndex,
                                   long key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return binarySearch0(a, fromIndex, toIndex, key);
    }
    
	private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

JDK中的二分查找，是通过一个while循环来不断缩小查找范围，对边界无额外处理，只要存在区间就可以继续。借鉴这种写法重新编码提交了一版，数据表现和上一版代码一致：

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

    public int binarySearch(int[] n, int target, int startp, int endp) {
        while(startp <= endp) {
            int mid = (startp + endp) >>> 1;
            int midVal = n[mid];

            if(target < midVal) {
                endp = mid - 1;
            } else if(target > midVal) {
                startp = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    } 
}

二分查找作为最基础的算法，还是要做到非常熟练才行，建议手写多练习几遍。