你所知道的查找算法？

⼆分查找法

算法简介

折半查找算法要求查找表的数据是线性结构存储，还要求查找表中的顺序是由⼩到⼤排序（由⼤到⼩排序）

算法思路及实现

1. ⾸先设两个指针，low和height，表示最低索引和最⾼索引
2. 然后取中间位置索引middle，判断middle处的值是否与所要查找的数相同，相同则结束查找，middle处的值⽐所要查找的值⼩就把low设为middle+1，如果middle处的值⽐所要查找的值⼤就把height设为middle-1
3. 然后再新区间继续查到，直到找到或者low>height找不到所要查找的值结束查找

functions binarySearch (arr, target) {
    let max = arr.length - 1
    let min = 0
    while (min <= max) {
    let mid = Math.floor((max + min) / 2)
    if (target < arr[mid]) {
    max = mid - 1
    } else if (target > arr[mid]) {
    min = mid + 1
    } else {
    return mid
    }
    }
    return -1
}

算法分析

最佳情况：T(n) = O(logn) 最差情况：T(n) = O(logn) 平均情况：T(n) = O(logn)

线性查找

算法简介及实现

线性查找很简单,只需要进⾏简单的遍历即可.

const linearSearch = (arr, target) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i
}
}
return -1
}

算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n) 平均情况：T(n) = O(n)