好久没有和大家见面了，最近一周每天晚上都在搬家，一直没有时间。今天来给大家分享一道面试的时候，被问及的一道算法题：一个数组，有一百万个元素，每个元素都是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
二分法与这道算法题就为大家说到这里，欢迎大家来交流，指出文中一些说错的地方，让我加深认识。
谢谢大家！
网友评论