JavaScript - 資料結構與演算法:二元搜尋 (Binary Search) 與線性搜尋 (Linear Search)

最近一直聽到演算法這幾個字，但一直都沒有去深度研究這一系列。

Youtube 上面放很久關於 LeetCode 的 Tree Node ，看了一下，還是搞不太懂怎麼讓一個陣列實現從 root 變樹狀結構的，於是我決定先來研究一下之前聽到的 Binary Search ，但是卻一直沒有學習過。

線性搜尋 (Linear Search)

所謂的線性搜尋，是依照 index 的順序，依序搜尋，直到找尋到目標後返回位置，也就是陣列的長度有多少，會在迴圈內依次增加 index ，最後找到搜尋的目標所在，如果沒有找到該目標，則返回 -1 ，其實就是跟 JavaScript 的 findIndex() 是一樣的方法。

僅管 numbers 的陣列是沒有經過排序的資料，線性搜尋都會直接依照順序，挨家挨戶比對，直到返回最終結果，也就是 線性成長 O(n) 的方式。

const numbers = [52, -33, 1.5, 38, -1.23, 7, 125]
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i
    }
    return -1
}
linearSearch(numbers, 38)
// Output: 3
linearSearch(numbers, 151)
// Output: -1

下面的範例是使用 findIndex() 的方法，是不是效果和上面一樣。

numbers.findIndex( n => n === 5)
// Output: 4
numbers.findIndex( n => n === 7)
// Output: -1

線性搜尋 (Linear Search) 比較合適使用在處理資料沒那麼龐大的地方，如果當有幾百萬、幾兆筆資料時，所耗時的搜尋時間和等待的時間就會拉長，如果時間過長，有可能會以為是不是資料庫當機了或是伺服器掛點了，這時候線性搜尋 (Linear Search) 的方法，就不是那麼好用了。

二元搜尋 (Binary Search)

如何在龐大的資料中，搜尋到對的資料，所花費的時間長短，會影響搜尋的效能與時間。二元搜尋 (Binary Search) 的方法，等於是將陣列搜尋的方法，用二分法的方式，尋找從中間比對的方法，去獲取目標的位置，也就是對數成長 O(logN)，比較像是 2 的 n 次方。

從下面的例子，我們可以看得出，一開始 start 的起始位子是在 0 ， end 的位子則是陣列的總長度減去 1 ，然後使用 while() 迴圈去判斷，如果 end 大於等於 start 的話，就執行迴圈裡面的內容。

function binarySearch (arr, target) {
    let start = 0
    let end = arr.length - 1

    while(end >= start) {
        let mid = Math.floor((start+end) / 2)
        if (arr[mid] === target) return mid
        if (arr[mid] < target) start = mid + 1
        if (arr[mid] > target) end = mid - 1
    }

    return -1
}

一開始陣列會先從 start 和 end 相加再除以 2 ，並去除小數點後，就是陣列從中間切開，去比對左右二邊，哪一個更接近目標的值，然後去反覆比對尋找，而且是將 start 從中間遞增的方式和 end 是從中間遞減的方式，讓每次的起始位子和結束位子都不一樣，直接找到正確的目標為止。

比如，一百萬除以二，下一次搜尋的目標就從一百萬直接從五十萬內開始搜尋，然後是二十五萬、十二萬五千…直到縮小範圍為止，中間大概只花了七次，就如剛剛說的，線性搜尋 (Linear Search) 是依陣列的總長度，一個一個去搜尋比對的，也就是一百萬次的方式找尋目標，如果該目標最後不存在，那搜尋一百萬次和最多只搜尋 20 次的時間效率相比，就相差了很多倍。

我們使用一個已經排序好的陣列，來使用 binarySearch() 的方法，千萬不可以使用沒有經過排序好的陣列來使用二元搜尋，這樣會造成資訊不對等，且也會花費掉許多時間去比對，就沒有任何義意了。

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 33, 44, 55, 66, 189, 253, 371, 3926, 2353242]
binarySearch(numbers, 10)
// Output: 9;
binarySearch(numbers, 189)
// Output: 15;
binarySearch(numbers, 2383)
// Output: -1;

我們來實測一下，建立一個千萬級別的資料，再使用 binarySearch() 的方法來找尋目標的位子。

let bigData = []
for (let i = 0; i < 10000000; i++) { bigData.push( (i+1) * 2 ) }

// 測試搜尋最左邊，中間和最右邊邊際存在的內容
binarySearch(bigData, 2)
// Output: 0
binarySearch(bigData, 10000000)
// Output: 4999999
binarySearch(bigData, 12345678)
// Output: 6172838
binarySearch(bigData, 20000000)
// Output: 9999999

// 測試搜尋最左邊，中間和最右邊邊際不存在的內容
binarySearch(bigData, 1)
// Output: -1
binarySearch(bigData, 7201)
// Output: -1
binarySearch(bigData, 19999997)
// Output: -1

如果想知道實際運作效率的時間，可以使用下面的方法測試，就可以知道實際上所消耗的時間差距多少，上面的一千萬可以再多加 0 ，去比對時間搜尋結果的時間。

console.log("線性搜尋耗費的時間")
console.time()
console.log("搜尋 19999997 的位子", linearSearch(numbers, 19999997))
console.timeEnd()

console.log("二元搜尋耗費的時間")
console.time()
console.log("搜尋 19999997 的位子", binarySearch(numbers, 19999997))
console.timeEnd()

結語

對這篇文章有興趣的人，可以去看看彭彭老師的教學，我曾經在台大上過他的前端教學課程，我也是透過他的教學影片，才搞懂二元搜尋 (Binary Search) 和線性搜尋 (Linear Search)
JavaScript 資料結構與演算法：二元搜尋法 Binary Search 實作與分析 - 彭彭直播 at 2020/09/08