二分搜尋(Binary Search)是查找有序資料的經典演算法:每次拿中間元素與目標比較,據此把搜尋範圍砍半,因此效率遠優於逐個比對。
使用前提只有一個:陣列必須是已經排序好的。
下面用遞迴的方式實作:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<script type="text/javascript">
// window.alert(Math.floor(5.7)); // 向下取整 輸出 5
// 二分查找法 陣列必須是有序的
function binarySeach(arr, findval, leftIndex, rightIndex) {
// 找到中間的值
var midIndex = Math.floor((leftIndex + rightIndex) / 2);
var midval = arr[midIndex];
// 防止無窮遞歸
if (leftIndex > rightIndex) {
// 說明找不到
document.writeln("找不到");
return;
}
// 進行查找
if (midval > findval) {
// 在左邊找
binarySeach(arr, findval, leftIndex, midIndex - 1);
} else if (midval < findval) {
// 說明往右邊找
binarySeach(arr, findval, midIndex + 1, rightIndex);
} else {
// 找到了 輸出或者返回
document.writeln("找到了,下標為:" + midIndex);
return;
}
}
var arr = [1, 3, 12, 21, 24, 44, 54, 67];
binarySeach(arr, 67, 0, arr.length - 1);
</script>
</head>
<body></body>
</html>
整數除法:用 Math.floor() 把索引夾在中點,確保 midIndex 一定是整數。
遞迴的終止條件:leftIndex > rightIndex 代表範圍已經交叉,說明目標不存在。少了這個判斷,遞迴會無止境地進行下去。
範圍的收斂方式:往左找時右端點是 midIndex - 1,往右找時左端點是 midIndex + 1。這裡必須加減一,否則在只剩兩個元素的情況下會陷入無限遞迴。
以 [1, 3, 12, 21, 24, 44, 54, 67] 搜尋 67 為例,第一次取索引 3(值 21),目標更大所以往右;接著取索引 5(值 44),仍往右;最後取到索引 7,命中並輸出下標。