搜索算法

顺序

O(n) O(1)

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

function sequentialSearch(nums: number[], target: number): number {
  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))

二分

❗️ 数组必须是有序的

LeetCode 704. 二分查找 简单

分治 O(logn) O(1)

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

function search(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const mid = left + Math.round((right - left) / 2)
    const item = nums[mid]
    if (target > item) {
      left = mid + 1
    } else if (target < item) {
      right = mid - 1
    } else {
      return mid
    }
  }

  return -1
}

console.log('🌰', search([1, 2, 3, 6, 19, 44, 50], 19))
console.log('🌰', search([-1, 0, 3, 5, 9, 12], 2))