[TOC] # 順序搜索 順序或線性搜索是最基本的搜索算法。它的機制是，將每一個數據結構中的元素和我們要找的元素做比較。順序搜索是最低效的一種搜索算法。 <br> ## 動圖演示  <br> ## 代碼 ~~~ /** * Linear search implementation. * * @param {*[]} array * @param {*} seekElement * @return {number[]} */ function linearSearch(array, seekElement) { const foundIndices = [] array.forEach((element, index) => { if (element === seekElement) { foundIndices.push(index) } }) return foundIndices } ~~~ <br> <br> # 二分搜索 二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。 <br> ## 步驟 * 首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較 * 如果兩者相等，則查找成功； * 否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。 * 重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。 <br> ## 圖片  <br> ## 代碼 ~~~ function binary_search(arr, item) { let low = 0 let high = arr.length - 1 while (low < high) { var mid = Math.floor((high + low) / 2) if (arr[mid] === item) return mid if (arr[mid] > item) { high = mid - 1 } if (arr[mid] < item) { low = mid + 1 } } return -1 } ~~~ <br> ## 復雜度 **時間復雜度**：`O(log(n))` —— 因為我們每進行一次迭代就將搜索區域劃分為兩部分