好久没有和大家见面了，最近一周每天晚上都在搬家，一直没有时间。今天来给大家分享一道面试的时候，被问及的一道算法题：一个数组，有一百万个元素，每个元素都是0-9的数字，而且有序，让统计出有多少个5，当时已经连续面试了4个多小时，头脑很乱，在面试官的一再提醒有序下，想起来有序就要用二分查找法，当时给出的大致思路就是利用二分法找到最后一个小于5的元素下标和第一个大于5的元素下标，相减就得出了5的个数，面试完了，一直没有时间去实现一下这道题，今天顺便来聊一聊二分法查找法，并实现一下这道面试题。

二分查找法原理

简单说一下二分查找法的原理：二分查找法就是，在数组有序的前提下，将要查找的元素与数组中的中间元素比较，如果小于中间元素，就在数组前半段继续查找，如果大于中间元素，就在数组后半段查找，否则数组中间的元素就是要查找的元素。

利用Java实现二分查找法的栗子

本栗子中，参考了java.util包中Arrays类中的二分查找法的实现，大家可以直接使用Arrays类中的二分查找方法：

package ftd.edu.search;

/**
 * @Description: .
 * @Author: ZhaoWeiNan .
 * @CreatedTime: 2017/7/4 .
 * @Version: 1.0 .
 */
public class Search {


    public static int binarySearch(int[] array,Integer key){

        if (array == null || array.length < 1){
            //数组为空返回-1
            return -1;
        }

        int left = 0;
        int right = array.length - 1;
        int middle;
        int middleValue;
        while (left <= right) {
            //>>>这个运算符大致讲一下，
            //是无符号右移运算符，是把二进制的数，向右移动一位
            //比如说  4 对应的二进制是： 100  右移一位是 10 转换成十进制是 2
            //比如说  5 对应的二进制是： 101  右移一位是 10 转换成十进制是 2
            //>>>1 就是相当于java中做了除以2的计算
            //算出中间的下标
            middle = (left + right) >>> 1;
            //取出中间的元素
            middleValue = array[middle];

            //如果大于中间元素在右边里面找
            if (middleValue < key)
                left = middle + 1;
            //如果小于中间元素在左边里面找
            else if (middleValue > key)
                right = middle - 1;
            //等于就找到了
            else
                return middle;
        }
        //没找到返回-1
        return -1;

    }

    public static void main(String[] args){
        int[] array = new int[]{1,3,5,6,7,8,9,10,11};
        System.out.println(binarySearch(array,5));
    }
}

2

Process finished with exit code 0

利用二分查找法实现面试中的那道算法题

按照当时的思路，利用二分法找到最后一个小于5的元素下标和第一个大于5的元素下标，相减就得出了5的个数，分解一下：

先利用二分法求出最后一个小于5的元素下标

这里需要对二分法改造一下：

 /**
     * 查找最后一个小于key的元素下标
     * @param array
     * @param key
     * @return
     */
    public static int binarySearchMin(int[] array,Integer key){

        if (array == null || array.length < 1){
            //数组为空返回-1
            return -1;
        }

        int left = 0;
        int right = array.length - 1;
        int middle;
        int middleValue;
        while (left <= right) {

            middle = (left + right) >>> 1;
            //取出中间的元素
            middleValue = array[middle];

            //因为要找出小于key的最后一个元素的下标，所以对这边的逻辑改造了一下
            //如果key小于等于中间元素在左边数组里面找
            if (middleValue >= key)
                right = middle - 1;
            //反之在右边数组找
            else
                left = middle + 1;
        }
        //返回右面的,就是小于key的最后一个元素的下标
        return right;

    }

再利用二分法求出第一个大于5的元素下标

这里需要对二分法改造一下：

/**
     * 查找第一个大于key的元素下标
     * @param array
     * @param key
     * @return
     */
    public static int binarySearchMax(int[] array,Integer key){

        if (array == null || array.length < 1){
            //数组为空返回-1
            return -1;
        }

        int left = 0;
        int right = array.length - 1;
        int middle;
        int middleValue;
        while (left <= right) {

            middle = (left + right) >>> 1;
            //取出中间的元素
            middleValue = array[middle];

            //因为要找出小于key的最后一个元素的下标，所以对这边的逻辑改造了一下
            //如果大于等于中间元素在右边里面找
            if (middleValue <= key)
                left = middle + 1;
            //如果小于中间元素在左边里面找
            else
                right = middle - 1;
        }
        //返回右面的,就是小于key的最后一个元素的下标
        return left;

    }

最后结果：

public static void main(String[] args){
        int[] array = new int[]{1,3,5,6,7,8,9,10,11};
        int[] array1 = new int[]{1,1,1,1,1,3,3,3,3,3,3,5,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,9,9,10,10,10,11,11,11,11};
        System.out.println(binarySearch(array,5));
        System.out.println(binarySearchMin(array1,5));
        System.out.println(binarySearchMax(array1,5));

    }

相减就是我们需要的结果

本文的中代码已经上传到开源中国，有兴趣的小伙伴可以拿走：https://git.oschina.net/zhaoweinan/binarysearch.git

二分法与这道算法题就为大家说到这里，欢迎大家来交流，指出文中一些说错的地方，让我加深认识。
谢谢大家！