二分搜尋(Binary Search)是資料結構裡最經典的查找策略之一:前提是資料已排序,每次拿中間值跟目標比,比目標小就往右半邊找、比目標大就往左半邊找,一步砍掉一半,因此效率是 O(log n)。下面用 JavaScript 寫成遞迴版本给大家參考。
<!DOCTYPE html> <html> <head> <title>demo</title> <style type="text/css"> </style> <script type="text/javascript"> var binarySearch = function(array, start, stop, num) { if(stop - start == 1) { if(array[start] == num) { return start; } if(array[stop] == num) { return stop; } return -1; } var center = Math.floor((start + stop)/2); if(num != array[center]) { return num > array[center] ? binarySearch(array, center, stop, num) : binarySearch(array, start, center, num); } return center; } var array = [1,4,6,12,15,20]; document.writeln(binarySearch(array, 0, array.length, 2)); </script> </head> <body> </body> </html>
執行結果為:
-1
這裡回傳 -1 是因為陣列裡確實沒有 2,代表「查無此元素」,這也是二分搜尋慣用的找不到標記。
讀這段程式碼時有兩處值得留意。第一,遞迴的終止條件寫成 stop - start == 1,也就是區間收斂到只剩兩個元素時,逐一比對後結束,避免無限遞迴。第二,呼叫時傳入的 stop 是 array.length 而非 length - 1,這是配合上述終止條件的刻意設計;若改成標準的閉區間寫法,兩邊都要一起調整,否則會漏掉尾端元素。
實務上當然也可以寫成 while 迴圈的迭代版本,通常效能更好、也不必擔心遞迴深度。不過遞迴寫法在表達「每次砍一半」這件事上更直觀,理解演算法本質時很有幫助。
希望這次的示範對大家學習 JavaScript 演算法有所幫助。