【算法】查找

概念知识

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）
查找算法分类：
1）静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。
平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。是衡量查找算法效率的最主要标准。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi * Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。

1. 顺序查找【无序查找】

思想：

从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值value相比较，若相等则表示查找成功，函数返回该数据元素在线性表中的位置；若扫描结束仍没有找到关键字等于value的结点，表示查找失败，则函数返回-1。
说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

代码：

function sequenceSearch(arr, value) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === value) return i;
    }
    return -1;
}
var a = [25, 2, 63, 48, 42, 10, 5, 55];
console.log(sequenceSearch(a, 48));

时间复杂度：

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n)。

2. 二分查找【有序查找】

思想：

二分查找也称为是折半查找，属于有序查找算法。用给定值value先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据value与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
说明：元素必须是有序的，如果是无序的则要先进行排序操作。

代码：（分为递归 + 非递归）

//递归
function binarySearch1(arr, value, start, end) {
    if (start > end) {
        return -1;
    }
    var start = start || 0;
    var end = end || arr.length - 1;
    var mid = Math.floor((start + end) / 2);
    if (arr[mid] == value) return mid;
    if (arr[mid] > value) {
        end = mid - 1;
        return binarySearch(arr, value, start, end);
    } else {
        start = mid + 1;
        return binarySearch(arr, value, start, end);
    }
    return -1;
}

//非递归
function binarySearch2(arr, value) {
    var start = 0,
        end = arr.length;
    while (start <= end) {
        var mid = Math.floor((start + end) / 2);
        if (arr[mid] === value) return mid;
        else if (arr[mid] > value) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

时间复杂度：

最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(logn)

3. 插值查找【有序查找】

思想：

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。差值查找也属于有序查找。
二分查找：mid=low+1/2*(high-low);
插值查找将查找的点改进为如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
（key到a[low]的距离占整个区间的距离，值小靠左，值大靠右）

代码：

function insertSearch(arr, value, start, end) {
    var start = start || 0;
    var end = end || arr.length - 1;
    var mid = Math.floor(start + (value - arr[start]) / (arr[end] - arr[start]) * (end - start));
    if (arr[mid] === value) return mid;
    if (value < arr[mid]) {
        return insertSearch(arr, value, start, mid - 1);
    } else {
        return insertSearch(arr, value, mid + 1, end);
    }
    return -1;
}

时间复杂度：

查找成功或者失败的时间复杂度均为O(log(logn))。

4. 二叉排序树查找【动态查找】

二叉排序树概念：

或是一棵空树；
或者是具有如下性质的非空二叉树：
（1）左子树的所有结点均小于根的值；
（2）右子树的所有结点均大于等于根的值；
（3）它的左右子树也分别为二叉排序树。

思想：

类似于有序表中的折半查找。
首先跟根的key比较，若小于根的key，则与根的左子树的key比较，以此类推；若大于根的key，则与根的右子树的key比较，以此类推。
注：使用该算法，需要先创建二叉排序树。

复杂度：

在一般情况下，二叉排序树的平均查找长度为O(log₂n)。
在最坏情况下，二叉排序树的平均查找长度为O(n)。

5. 哈希查找

概念知识：

（1）哈希函数：数据元素的关键字和该数据元素的存放位置之间的映射函数
（2）哈希表（散列表）：通过哈希函数来确定数据元素存放位置的一种特殊表结构。
（3）哈希冲突有关因素：
- 装填因子α 。装填因子是指哈希表中已存入的数据元素个数ｎ与哈希地址空间大小ｍ的比值，即α＝ｎ/ｍ，α越小，冲突的可能性就越小，但哈希表中空闲单元的比例就越大； α越大（最大可取1）时，冲突的可能性就越大，但哈希表中空闲单元的比例就越小，存储空间的利用率就越高。
- 与所采用的哈希函数有关。
- 与解决哈希冲突的哈希冲突函数有关。
（4）哈希函数构造方法：
- 除留余数法：h(K) = K mod m
- 直接定址法：h(K) =K 或 h(K) =a* K + b
（5）哈希冲突解决方法：
一、开放定址法
- 线性探查法：

-平方探查法：

二、链表法
- 拉链法：

拉链法
- 公共溢出区：
已知一组关键字为（19,14,23,1,68,20,84,27,55,40,10,79）；
哈希函数为H(key)=key MOD 13 ，冲突解决方法为公共溢出区。
公共溢出区
计算平均查找长度：ASL=(5×1 + 4×2 + 3 + 4 + 5)/12=2.08