好久沒(méi)有和大家見(jiàn)面了揉抵，最近一周每天晚上都在搬家，一直沒(méi)有時(shí)間嗤疯。今天來(lái)給大家分享一道面試的時(shí)候冤今，被問(wèn)及的一道算法題：一個(gè)數(shù)組，有一百萬(wàn)個(gè)元素茂缚，每個(gè)元素都是0-9的數(shù)字戏罢，而且有序，讓統(tǒng)計(jì)出有多少個(gè)5脚囊，當(dāng)時(shí)已經(jīng)連續(xù)面試了4個(gè)多小時(shí)龟糕，頭腦很亂，在面試官的一再提醒有序下悔耘，想起來(lái)有序就要用二分查找法讲岁，當(dāng)時(shí)給出的大致思路就是利用二分法找到最后一個(gè)小于5的元素下標(biāo)和第一個(gè)大于5的元素下標(biāo)，相減就得出了5的個(gè)數(shù)衬以，面試完了缓艳，一直沒(méi)有時(shí)間去實(shí)現(xiàn)一下這道題，今天順便來(lái)聊一聊二分法查找法看峻，并實(shí)現(xiàn)一下這道面試題阶淘。
二分查找法原理
簡(jiǎn)單說(shuō)一下二分查找法的原理：二分查找法就是，在數(shù)組有序的前提下备籽，將要查找的元素與數(shù)組中的中間元素比較舶治，如果小于中間元素，就在數(shù)組前半段繼續(xù)查找车猬，如果大于中間元素霉猛，就在數(shù)組后半段查找，否則數(shù)組中間的元素就是要查找的元素珠闰。
利用Java實(shí)現(xiàn)二分查找法的栗子
本栗子中惜浅，參考了java.util包中Arrays類(lèi)中的二分查找法的實(shí)現(xiàn)，大家可以直接使用Arrays類(lèi)中的二分查找方法：
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){
//數(shù)組為空返回-1
return -1;
}
int left = 0;
int right = array.length - 1;
int middle;
int middleValue;
while (left <= right) {
//>>>這個(gè)運(yùn)算符大致講一下伏嗜，
//是無(wú)符號(hào)右移運(yùn)算符坛悉，是把二進(jìn)制的數(shù)，向右移動(dòng)一位
//比如說(shuō) 4 對(duì)應(yīng)的二進(jìn)制是： 100 右移一位是 10 轉(zhuǎn)換成十進(jìn)制是 2
//比如說(shuō) 5 對(duì)應(yīng)的二進(jìn)制是： 101 右移一位是 10 轉(zhuǎn)換成十進(jìn)制是 2
//>>>1 就是相當(dāng)于java中做了除以2的計(jì)算
//算出中間的下標(biāo)
middle = (left + right) >>> 1;
//取出中間的元素
middleValue = array[middle];
//如果大于中間元素在右邊里面找
if (middleValue < key)
left = middle + 1;
//如果小于中間元素在左邊里面找
else if (middleValue > key)
right = middle - 1;
//等于就找到了
else
return middle;
}
//沒(méi)找到返回-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
利用二分查找法實(shí)現(xiàn)面試中的那道算法題
按照當(dāng)時(shí)的思路承绸，利用二分法找到最后一個(gè)小于5的元素下標(biāo)和第一個(gè)大于5的元素下標(biāo)裸影，相減就得出了5的個(gè)數(shù)，分解一下：
先利用二分法求出最后一個(gè)小于5的元素下標(biāo)
這里需要對(duì)二分法改造一下：
/**
* 查找最后一個(gè)小于key的元素下標(biāo)
* @param array
* @param key
* @return
*/
public static int binarySearchMin(int[] array,Integer key){
if (array == null || array.length < 1){
//數(shù)組為空返回-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];
//因?yàn)橐页鲂∮趉ey的最后一個(gè)元素的下標(biāo)军熏，所以對(duì)這邊的邏輯改造了一下
//如果key小于等于中間元素在左邊數(shù)組里面找
if (middleValue >= key)
right = middle - 1;
//反之在右邊數(shù)組找
else
left = middle + 1;
}
//返回右面的,就是小于key的最后一個(gè)元素的下標(biāo)
return right;
}
再利用二分法求出第一個(gè)大于5的元素下標(biāo)
這里需要對(duì)二分法改造一下：
/**
* 查找第一個(gè)大于key的元素下標(biāo)
* @param array
* @param key
* @return
*/
public static int binarySearchMax(int[] array,Integer key){
if (array == null || array.length < 1){
//數(shù)組為空返回-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];
//因?yàn)橐页鲂∮趉ey的最后一個(gè)元素的下標(biāo)轩猩，所以對(duì)這邊的邏輯改造了一下
//如果大于等于中間元素在右邊里面找
if (middleValue <= key)
left = middle + 1;
//如果小于中間元素在左邊里面找
else
right = middle - 1;
}
//返回右面的,就是小于key的最后一個(gè)元素的下標(biāo)
return left;
}
最后結(jié)果：
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));
}
本文的中代碼已經(jīng)上傳到開(kāi)源中國(guó)，有興趣的小伙伴可以拿走：https://git.oschina.net/zhaoweinan/binarysearch.git
二分法與這道算法題就為大家說(shuō)到這里，歡迎大家來(lái)交流均践，指出文中一些說(shuō)錯(cuò)的地方晤锹，讓我加深認(rèn)識(shí)。
謝謝大家彤委！
