[Algorithm] Binary Search (二分搜尋法)
Binary Search 說明
以下轉自維基 二分搜尋演算法
在有序陣列中搜尋某一特定元素的搜尋演算法
搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半
每次都從中位數切半，尋找有沒有包含指定數字
範例程式碼
Ruby 範例
附上 Ruby 的 online sandbox，有興趣可以把 code 貼進去玩玩看
target = 12
a = [0, 2, 4, 6, 8, 10, 12, 14, 16]
def binary_search(array, target)
first = 0
last = array.length - 1
while first <= last
i = (first + last) / 2
if array[i] == target
return "#{target} 在 array 第 #{i} 筆"
elsif array[i] > target
last = i - 1
else array[i] < target
first = i + 1
end
end
return "#{target} 不存在該 array"
end
puts binary_search(a, target)
結果如下
JavaScript 範例
JavaScript 的 online sandbox，有興趣可以把 code 貼進去玩玩看
target = 12
a = [0, 2, 4, 6, 8, 10, 12, 14, 16]
function binarySearch(array, target) {
var first = 0;
var last = array.length - 1;
var guess;
while(first <= last) {
i = Math.floor((first + last) / 2);
if (array[i] === target) {
return target + " 在 array 第 " + i + " 筆";
} else if (array[i] < target) {
first = i + 1;
} else {
last = i - 1;
}
}
return target + " 不存在該 array";
}
console.log(binarySearch(a, target))
結果如下
