Stan Blog

記錄學習到的東西

[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)

結果如下

螢幕快照 2020-08-31 16 41 42

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))

結果如下

螢幕快照 2020-08-31 16 52 07

Comments

comments powered by Disqus