二分查找就是每次都找中間數(shù)掀泳，然后跟要查找的數(shù)對(duì)比懒熙。
比如有這樣一個(gè)數(shù)組：
var s = [1,2,3,4,5,6,7,8,9,10,104,234]; （排過序的）
你要從中間找到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; ? ? //沒找到茴肥，將中間值作為最大值，繼續(xù)執(zhí)行
? ? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ? ? ? a = middle + 1; ? //沒找到荡灾，將中間值作為最小值瓤狐，繼續(xù)執(zhí)行
? ? ? ? ? ? ? }
? ? ? }
? ? ? return -1; ?//數(shù)組里沒有這個(gè)數(shù)，返回-1批幌；
}
我們要找到104在數(shù)組s里所對(duì)應(yīng)的下標(biāo)础锐，就只需要調(diào)用函數(shù)
var? res = BinarySearch(s,104);
學(xué)習(xí)了二分法，來個(gè)實(shí)例：還是剛剛那個(gè)數(shù)組：
var s = [1,2,3,4,5,6,7,8,9,10,104,234];
要從里面找到2個(gè)數(shù)荧缘，要求他們的相加等于110皆警，怎么做？
先說思想截粗，二分法是找一個(gè)數(shù)信姓，題目要求是找二個(gè)數(shù)，怎么辦绸罗？我們要把問題轉(zhuǎn)化到找一個(gè)數(shù)上意推，遍歷數(shù)組s，每次遍歷的時(shí)候得到其中一個(gè)數(shù)s[i],然后去找另外一個(gè)數(shù)珊蟀，我們要找相加等于110的數(shù)菊值，那另外一個(gè)數(shù)其實(shí)就等于110-s[i]，說到這里是不是已經(jīng)明白了系洛？
沒明白不要緊俊性，貼代碼，請(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定页，有的話就說明a的假設(shè)成立了
? ? ? ? if (n != -1) { //上面說了n==-1的時(shí)候?qū)嶋H上就是沒找到，所以不等于-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);
