查找

二分查找

思路： 有序数组中找到 中位数 根据 查找目标值和中位数的比较 然后 递归查找对应范围的数组

时间复杂度：O(log(2n))

// 有序数组的二分查找
function binarySearch(arr, target, start, end) {
    const middleIndex = start + ~~((end - start) / 2);
    if(start === end && arr[middleIndex] !== target) {
        return null
    }
    if(arr[middleIndex] > target) {
        return binarySearch(arr, target, start, middleIndex - 1)
    } else if(arr[middleIndex] < target) {
        return binarySearch(arr, target, middleIndex + 1, end)
    } else {
        return middleIndex
    }
}
const testArr = [1,2,3,4,5,6,7,8,9]
console.log(binarySearch(testArr, 9 ,0 ,testArr.length))

散列表（哈希表）

js 对象 是基于哈希表的, 将key 转换成数组索引储存起来

const obj = {
name : 25
}

散列函数 fn

索引位置 = fn(obj.key)

如何解决 计算的索引冲突
将索引地址指向一个链表 散列函数计算出相同的索引 就向链表加 一个节点 节点存储了 对应的键值对