常见数据结构与算法-JavaScript版(查找篇)

362 阅读3分钟

1.查找的定义

在计算机科学中定义为:在一些(有序的/无序的)数据元素中,通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。

2.顺序查找

从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相同,则查找成功;如果直到最后一个(或第一个)记录,关键字和给定值比较都不相等,则查找不成功。

顺序查找的时间复杂度为O(n)。

    function orderSearch(target, arr) {
        // 也可以使用for循环
        let i = arr.length - 1;
        while (arr[i] != target && i >= 0) {
            i--;
        }
        return i;
    }

3.二分查找

二分查找也叫折半查找,它的前提是线性表中必须是关键码有序(一般是从小到大有序),线性表必须采取线性存储。二分查找是在有序表中,取中间记录作为比较对象,若给定值与中间记录关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区进行查找;若给定值大于中间记录的关键字,则在中间记录的右半区进行查找。不断重复上述过程,直到查找成功或所有查找区域无记录,查找失败。

    function halfSearch(target, arr) {
        let low = 0;
        let high = arr.length - 1;
        let i = 0;
        // 当low>high时说明此数不存在,循环结束,返回-1,存在等号是因为target有可能出现在第一位或最后一位
        while (low <= high) {
            i = parseInt((low + high) / 2);
            if (target < arr[i]) {
                // high 不能等于i,target已经与arr[i]比较过(出现死循环 low=high,但arr[i]!=target)
                high = i - 1;
            } else if (target > arr[i]) {
                // low 不能等于i,target已经与arr[i]比较过i
                low = i + 1;
            } else {
                return i;
            }
        }
        return -1;
    }

4.斐波那契查找

斐波那契查找与二分查找的原理和时间复杂度相同,只是mid的值不再是中间值,而是mid=low+fib(k-1)-1。

详细原理可参考:www.cnblogs.com/han200113/p…

    function fibSearch(target, arr) {
        //简易斐波那契数列
        function fib(n) {
            if (n <= 1) {
                return 1;
            } else {
                return fib(n - 1) + fib(n - 2);
            }
        }
        var low = 0;
        //记录数组长度,后续会填充数组
        const temp = arr.length - 1;
        var k = 0;
        var mid = 0;
        while (fib(k) - 1 < arr.length) {
            k++;
        }
        high = fib(k) - 1;
        //将arr数组填充至fib(k)的长度
        for (var i = temp; i < high; i++) {
            arr.push(arr[temp]);
        }
        while (low <= high) {
            mid = low + fib(k - 1) - 1;
            if (arr[mid] < target) {
                low = mid + 1;
                k = k - 2;
            } else if (arr[mid] > target) {
                high = mid - 1;
                k = k - 1;
            } else {
                return mid <= temp ? mid : temp;
            }

        }
        return -1;
    }

5.二叉排序树

二叉排序树又叫二叉查找树。二叉排序树若它的左子树不为空,则左子树上所有节点的值均小于根节点的值;若它的右子树不为空,则右子树上所有节点的值均大于根节点的值;它的左右子树也是二叉排序树。

二叉排序树的数据结构见上篇。

//二叉排序树的查找
    function treeSearch(target, root) {
        if (root) {
            if (target == root.value) {
                return true;
            } else if (target < root.value) {
                return treeSearch(target, root.left);
            } else {
                return treeSearch(target, root.right);
            }
        } else {
            return false;
        }
    }