Binary Search – 二分查找详解编程语言

Problem

For a given sorted array (ascending order) and a target number, find thefirst index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge

If the count of numbers is bigger than 2322^{32}232, can your code work properly?

题解

对于已排序升序(升序)数组，使用二分查找可满足复杂度要求，注意数组中可能有重复值，所以需要使用类似lower_bound中提到的方法。

Java

class Solution { 
    /** 
     * @param nums: The integer array. 
     * @param target: Target to find. 
     * @return: The first position of target. Position starts from 0. 
     */ 
    public int binarySearch(int[] nums, int target) { 
        if (nums == null || nums.length == 0) { 
            return -1; 
        } 
 
        int start = -1, end = nums.length; 
        int mid; 
        while (start + 1 < end) { 
            // avoid overflow when (end + start) 
            mid = start + (end - start) / 2; 
            if (nums[mid] < target) { 
                start = mid; 
            } else { 
                end = mid; 
            } 
        } 
 
        if (end == nums.length || nums[end] != target) { 
            return -1; 
        } else { 
            return end; 
        } 
    } 
}

源码分析

1. 首先对输入做异常处理，数组为空或者长度为0。
2. 初始化 start, end, mid三个变量，这里start初始化为-1主要是考虑到end为1。注意mid的求值方法，可以防止两个整型值相加时溢出。
3. 使用迭代而不是递归进行二分查找，因为工程中递归写法存在潜在溢出的可能。
4. while终止条件应为start + 1 < end而不是start <= end，start == end时可能出现死循环。**即循环终止条件是相邻或相交元素时退出。**由于这里初始化时start < end，所以一定是start + 1 == end时退出循环。
5. 迭代终止时有两种情况，一种是在原数组中找到了，这种情况下一定是end, 因为start的更新只在nums[mid] < target.
6. 最后判断end和target的关系，先排除end为数组长度这种会引起越界的情况，然后再判断和目标值是否相等。

复杂度分析

时间复杂度 O(logn), 空间复杂度 (1).对于题中的 follow up, Java 中数组不允许使用 long 型，如果使用 long 型，那么数组大小可大 17GB 之巨！！几乎没法用。