搜索算法
顺序
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 并在选种值右边的子数组中寻找（较大）。