Sign in Subscribe
寫程式

「搜尋法」的解題技巧：線性搜尋與二分搜尋

在這篇文章中，我介紹了線性搜尋和二分搜尋這兩種基本的搜尋方法。線性搜尋適合於未排序的資料，而二分搜尋則需要預先排序的資料來提高效率。透過實例，我說明了如何在 JavaScript 中實現這兩種搜尋技術，並比較了它們的執行效率和適用情境，提供了一個更深入的搜尋法選擇依據。

Boison

• 2 min read
「搜尋法」的解題技巧：線性搜尋與二分搜尋
Photo by Mick Haupt / Unsplash

本文章會介紹些經典的搜尋法，比如線性搜尋法和二分搜尋法。

  • 線性搜尋: 一個一個找，從頭往尾直到找到為止
  • 二分搜尋: 前提是資料排序過。每次從正中間找比大小決定方向後，下次往左/右側的中間找

圖片來源: Binary Vs Linear Search Through Animated Gifs

const linearSearch = (arr, searchedValue) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === searchedValue) return i
  }
  return -1  // 尋找的元素不在陣列中
}

const binarySearch = (arr, searchedValue) => {
  let low = 0
  let high = arr.length - 1
  let mid
  while (low <= high) {
    mid = Math.floor((low + high) / 2)
    // 判斷搜尋左右方向  
    if (searchedValue < arr[mid]) {
      high = mid - 1   
    } else if (searchedValue > arr[mid]) {
      low = mid + 1
    } else {
      return mid  
    }
  }
  return -1  // 尋找的元素不在陣列中
}

let arr = [1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
linearSearch(arr, 23)  // 8
binarySearch(arr, 23)  // 8

延伸「指數搜尋（Exponential Search）」和「內插搜尋（Interpolation Search）」，可見 JavaScript 學演算法（二十）- 搜尋演算法 這篇文章。

資料來源演算法之二分搜尋 (Binary Search) & 線性搜尋 (Linear Search)用 JavaScript 學習資料結構與演算法 2：搜尋

Sign up for more like this.

Enter your email
Subscribe