二分查找就是每次都找中間數(shù)，然后跟要查找的數(shù)對(duì)比。

比如有這樣一個(gè)數(shù)組：

var s = [1,2,3,4,5,6,7,8,9,10,104,234]; （排過(guò)序的）

你要從中間找到104的下標(biāo)，怎么辦？

我們寫一個(gè)函數(shù)：

function BinarySearch(s,x){ ??

?//s為待查找數(shù)組，x為要查找的數(shù)

? ? ? ?var a = 0;

? ? ? ?var b = s.length-1;

? ? ? ?while(a<=b){ ?只要最小數(shù)不大于最大數(shù)，就一直執(zhí)行（好像是廢話）

? ? ? ? ? ? ? ? var middle = parseInt((a+b)/2); ? //取數(shù)組中間下標(biāo)

? ? ? ? ? ? ? ? if (x == s[middle]) {

? ? ? ? ? ? ? ? ? ? ? ?return middle; ?//找到了，返回結(jié)果

? ? ? ? ? ? ? ? }else if(x < s[middle]){

? ? ? ? ? ? ? ? ? ? ? b = middle-1; ? ? //沒(méi)找到，將中間值作為最大值，繼續(xù)執(zhí)行

? ? ? ? ? ? ? ?}else{

? ? ? ? ? ? ? ? ? ? ? a = middle + 1; ? //沒(méi)找到，將中間值作為最小值，繼續(xù)執(zhí)行

? ? ? ? ? ? ? }

? ? ? }

? ? ? return -1; ?//數(shù)組里沒(méi)有這個(gè)數(shù)，返回-1；

}

我們要找到104在數(shù)組s里所對(duì)應(yīng)的下標(biāo)，就只需要調(diào)用函數(shù)

var? res = BinarySearch(s,104);

學(xué)習(xí)了二分法，來(lái)個(gè)實(shí)例：還是剛剛那個(gè)數(shù)組：

var s = [1,2,3,4,5,6,7,8,9,10,104,234];

要從里面找到2個(gè)數(shù)，要求他們的相加等于110，怎么做？

先說(shuō)思想，二分法是找一個(gè)數(shù)，題目要求是找二個(gè)數(shù)，怎么辦？我們要把問(wèn)題轉(zhuǎn)化到找一個(gè)數(shù)上，遍歷數(shù)組s，每次遍歷的時(shí)候得到其中一個(gè)數(shù)s[i],然后去找另外一個(gè)數(shù)，我們要找相加等于110的數(shù)，那另外一個(gè)數(shù)其實(shí)就等于110-s[i]，說(shuō)到這里是不是已經(jīng)明白了？

沒(méi)明白不要緊，貼代碼，請(qǐng)看下面這個(gè)函數(shù)：

function searchTwoNum(s,x){ //傳數(shù)組s 和 兩個(gè)數(shù)之和x

? ? var dic;

? ? for(var i = 0; i < s.length;i++){

? ? ? ? var a = s[i]; ? //假設(shè)它是其中一個(gè)數(shù)

? ? ? ? var b = x - s[i]; ?//假設(shè)a的假設(shè)成立，那b就是另一個(gè)數(shù)

? ? ? ? var n = BinarySearch(s,b); //判斷是不是有b，有的話就說(shuō)明a的假設(shè)成立了

? ? ? ? if (n != -1) { //上面說(shuō)了n==-1的時(shí)候?qū)嶋H上就是沒(méi)找到，所以不等于-1時(shí)就找到了

? ? ? ? ? ? dic = {i:i,n:n,a:a,b:b};

? ? ? ? ? ? break; //找到了就不找了，跳出去

? ? ? ? }

? ? }

? ? return dic;

}

調(diào)用該函數(shù)，就可以找到要找的數(shù)：

var dic = searchTwoNum(s,110);

console.log(dic);