高频面试题之二分查找

二分查找二三事

引言

华为综合面碰到一个Cloud BU的大佬，唉，我明明面的是算法岗，这位大佬死抓我没有计算机基础不放，先是针对进程和线程死磕，而后怀疑我的开发水平，最后让我白板写二分查找，第一次白板写代码，很简单的题目，觉得最重要的是理清思路，先写个代码流程图再动手写代码相对会好点，以后面试再遇到白板编程就这么干吧，那天虽然把整体思路都理出来了，也写了个大概，但觉得还是不熟练，还是想复习下二分查找，二分查找说是简单，但其中关于边界的处理其实需要一波思考。这篇文章主要以一道lintcode题目，引发对二分查找的边界值的思考，以及一些变形题的实现，好吧，废话不多说，让我们开始吧…

一道LintCode题引发的思考

Guess Number Game
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.Every time you guess wrong, I’ll tell you whether the number is higher or lower.You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

样例
n = 10, I pick 4 (but you don’t know)
Return 4. Correct !

思路：一开始觉得这就是普通的二分查找问题，便写出如下代码：

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    /**
     * @param n an integer
     * @return the number you guess
     **/
    public int guessNumber(int n) {
        // Write your code here
        int left = 1;
        int right = n;
        while (left <= right) {
            int mid = (right + left) /2;
            int res = guess(mid);
            if (res == 0) {
                return mid;
            }
            if(res == -1) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
            
        }
        return -1;
    }
}

结果在下列测试用例时发生错误：

输入
2147483647
2147483647

期望答案
2147483647

提示
Your code ran too much time than we expected. Check your time complexity. Time limit exceeded usually caused by infinite loop if your time complexity is the best.

感觉是发生了溢出，因此将mid的计算方式改成如下形式：

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

这句简单的代码做了两个改进：

• 通过加的形式计算mid，而非直接除以2防止溢出
• 利用位运算进行除以2的计算更加方便
• 注意加号和>>的优先级，所以要加个括号

最后顺利AC。
这就引发了我对二分查找的思考。

先来看看什么是二分查找：

在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

常规套路：

public int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;
    //如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
    //1、下面循环的条件则是while(left < right)
    //2、循环内当 array[middle] > value 的时候，right = mid

    while (left <= right)  //循环条件，适时而变
    {
        int middle = left + ((right - left) >> 1);  //防止溢出，移位也更高效。同时，每次循环都需要更新。
        if (array[middle] > value)
            right = middle - 1;  //right赋值，适时而变
        else if (array[middle] < value)
            left = middle + 1;
        else
            return middle;
        //可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
        //如果每次循环都判断一下是否相等，将耗费时间
    }
    return -1;
}

题目变形

1. LintCode 14题

题目描述：

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

样例：
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

思路：
改变判断条件的临界值

代码：

public 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) {
        // write your code here
        if (nums.length == 0 || nums == null)
            return -1;
        
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        
        while (start <= end) {
            mid = start + ((end - start) >> 1);
            
            if (nums[mid] >= target)
                end = mid - 1;
            else
                start = mid + 1;
        }
        
       return nums[end+1] == target ? end + 1 : -1;
            
    }
}

2. LintCode 60题

题目描述：

给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
你可以假设在数组中无重复元素。

样例：
[1,3,5,6]，5 → 2

[1,3,5,6]，2 → 1

[1,3,5,6]， 7 → 4

[1,3,5,6]，0 → 0

代码：

public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: An integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
        if (A.length == 0 || A == null)
            return 0;
        
        int left = 0;
        int right = A.length - 1;
        int mid = 0;
        
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            
            if (A[mid] < target) {
                left = mid + 1;
            } else if (A[mid] >= target) {
                right = mid - 1;
            }
        }
        
        //right是数组最后一个元素的情况
        if (right == A.length - 1)
            return right+1;
            
        return A[right+1] >= target ? right+1 : right;
    }
}