[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))` —— 因为我们每进行一次迭代就将搜索区域划分为两部分