zhangdizhangdi

搜索算法

顺序

O(n) O(1)

将每一个数据结构中的元素和我们要找的元素做比较。

js
function sequentialSearch(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (target === nums[i]) {
      return i
    }
  }
  return -1
}
console.log('🌰', sequentialSearch([4, 3, 2, 4, 5], 3))
执行结果
🌰 1

二分

❗️ 数组必须是有序的

分治 O(logn) O(1)

(1) 选择数组的中间值。
(2) 如果选中值是待搜索值，那么算法执行完毕（值找到了）。
(3) 如果待搜索值比选中值要小，则返回步骤 1 并在选中值左边的子数组中寻找（较小）。
(4) 如果待搜索值比选中值要大，则返回步骤 1 并在选种值右边的子数组中寻找（较大）。