來自：韓子遲 - 博客園
作者：韓子遲【github：https://github.com/hanzichi 求關注】
連結：http://www.cnblogs.com/zichi/p/5118032.html
已獲轉載授權
什麼是二分查找就不多說了。
有時經常會碰到類似於從一個有序數組中找到元素第一次出現的位置，求一個有序數組中小於某元素的個數，將一個元素插入一個有序數組中，等等這樣的需求。比如 leetcode 315. Count of Smaller Numbers After Self 這道題用二分查找來解，就需要維護一個有序數組，不斷往數組中添加元素。這樣，傳統的 "從一個有序數組中求一個元素的位置，有則返回，沒有則返回 -1"，就需要變一下型了。
當然這完全可以用傳統的二分查找，找到一個相對來說 "比較正確" 的位置，然後從這個位置向左向右擴展，完全可以，而且複雜度也基本是一樣的，不過這樣的實現太 ugly 了。
為了以後能不用每次遇到二分查找就要推下解，特記錄如下，媽媽再也不用擔心我的二分查找了。
第一次出現某數的位置
如果沒找到，則返回 -1
可應對數據重複或者不重複兩種情況
a 數組需正序排列
二分代碼：
function binarySearch(a, target) {
var start = 0
, end = a.length - 1;
while(start <= end) {
var mid = ~~((start + end) >> 1);
if (a[mid] >= target)
end = mid - 1;
else
start = mid + 1;
}
return a[start] === target ? start : -1;
}
start 的最終結果永遠比 end 大 1。下同。
測試程序：
function _binarySearch(a, target) {
for (var i = 0, len = a.length; i < len; i++) {
if (a[i] === target)
return i;
if (a[i] > target)
return -1;
}
return -1;
}
最後一次出現某數的位置
換個思路，求有序數組中最後一次出現某數的位置，也就是求 "該數+1"（不管它在不在數列中） 第一次出現的位置 - 1。
function binarySearch(a, target) {
target += 1;
var start = 0
, end = a.length - 1;
while(start <= end) {
var mid = ~~((start + end) >> 1);
if (a[mid] >= target)
end = mid - 1;
else
start = mid + 1;
}
return a[end] === target - 1 ? end : -1;
}
這裡要注意的是找到的 end 索引可能是 -1，但是因為數組是特殊的對象，所以 a["-1"] 返回 undefined，正是利用了這個 hack，使得程序可以一行返回。同時要注意 target 在函數最開始已經自增過，所以需和 target-1 進行大小對比。
測試程序：
function _binarySearch(a, target) {
for (var i = 0, len = a.length; i < len; i++) {
if (a[i] === target && a[i + 1] !== target)
return i;
if (a[i] > target)
return -1;
}
return -1;
}
剛好比某數大的元素位置
跟求最後一次出現某數的位置類似。
function binarySearch(a, target) {
target += 1;
var start = 0
, end = a.length - 1;
while(start <= end) {
var mid = ~~((start + end) >> 1);
if (a[mid] >= target)
end = mid - 1;
else
start = mid + 1;
}
return start;
}
如 return 的數等於數組的長度，則表示數組內所有元素都比 target 元素小。
測試程序：
function _binarySearch(a, target) {
for (var i = 0, len = a.length; i < len; i++) {
if (a[i] > target)
return i;
}
return a.length;
}
剛好比某數小的元素位置
代碼：
function binarySearch(a, target) {
var start = 0
, end = a.length - 1;
while(start <= end) {
var mid = ~~((start + end) >> 1);
if (a[mid] >= target)
end = mid - 1;
else
start = mid + 1;
}
return end;
}
如果 return -1，則表示數組中沒有比 target 元素小的元素了（只能去找索引值為-1的元素了），這時要特別注意需要特判。
測試程序：
function _binarySearch(a, target) {
for (var i = a.length; i--; ) {
if (a[i] < target)
return i;
}
return -1;
}
總結
暫時只想到這四種應用場景。
測試程序的測試用例：
for (var i = 0; i < 1000; i++) { // 1000 組數據
var len = ~~(Math.random() * 500); // 數組長度 0-500
var a = [];
for (var j = 0; j < len; j++)
a.push(~~(Math.random() * 500)); // 數組元素大小 0-500
a.sort(function(a, b) {return a - b}); // sort
var target = ~~(Math.random() * 500); // target 元素
var ans1 = binarySearch(a, target);
var ans2 = _binarySearch(a, target);
if (ans1 === ans2)
console.log('ok');
else
alert('error!');
}
●本文編號136，以後想閱讀這篇文章直接輸入136即可。
●輸入m可以獲取到文章目錄。
更多推薦請看《15個技術類公眾微信》
涵蓋：程序人生、算法與數據結構、黑客技術與網絡安全、大數據技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。傳播計算機學習經驗、推薦計算機優秀資源：點擊前往《值得關注的15個技術類微信公眾號》
點擊閱讀原文，了解野狗