查找/检索 之 静态查找
发布在javascript描述数据结构和算法2015年3月15日view:5391数据结构和算法
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。
   数据的组织和查找是大多数应用程序的核心,而查找是所有数据处理中最基本、最常用的操作。特别当查找的对象是一个庞大数量的数据集合中的元素时,查找的方法和效率就显得格外重要。

查找设计的一些概念:
**查找表(Search Table)**:相同类型的数据元素(对象)组成的集合,每个元素通常由若干数据项构成。
**关键字(Key)**:数据元素中某个(或几个)数据项的值,它可以标识一个数据元素。若关键字能唯一标识一个数据元素,则关键字称为主关键字;将能标识若干个数据元素的关键字称为次关键字。
**查找/检索(Searching)**:根据给定的K值,在查找表中确定一个关键字等于给定值的记录或数据元素。
    ◆ 查找表中存在满足条件的记录:查找成功;结果:所查到的记录信息或记录在查找表中的位置。
    ◆ 查找表中不存在满足条件的记录:查找失败。

查找有两种基本形式:静态查找和动态查找。
**静态查找(Static Search)**:在查找时只对数据元素进行查询或检索,查找表称为静态查找表。
**动态查找(Dynamic Search)**:在实施查找的同时,插入查找表中不存在的记录,或从查找表中删除已存在的某个记录,查找表称为动态查找表。

根据存储结构的不同,查找方法可分为三大类:
 ①  顺序表和链表的查找:将给定的K值与查找表中记录的关键字逐个进行比较, 找到要查找的记录;
 ②  散列表的查找:根据给定的K值直接访问查找表, 从而找到要查找的记录;
 ③  索引查找表的查找:首先根据索引确定待查找记录所在的块 ,然后再从块中找到要查找的记录。

查找方法评价指标
查找过程中主要操作是关键字的比较,查找过程中关键字的平均比较次数(平均查找长度ASL:Average Search Length)作为衡量一个查找算法效率高低的标准。

因篇幅较多,这篇我主要讲得是静态查找。


顺序查找(Sequential Search)
1  查找思想
 从表的一端开始逐个将记录的关键字和给定K值进行比较,若某个记录的关键字和给定K值相等,查找成功;否则,若扫描完整个表,仍然没有找到相应的记录,则查找失败。

2  算法分析
假设查找每个记录的概率相等:
◆ 查找成功时的平均查找长度ASL:(n+1)/2
◆ 包含查找不成功时:查找失败的比较次数为n,若成功与不成功的概率相等,对每个记录的查找概率为Pi=1/(2n),则平均查找长度ASL:3(n+1)/4

3.算法实现
这是我们常见的遍历数组查找的一种方式,链表的顺序查找也和这个类似,就先省略了。

function sequentialSearch(sTable, key) {
    for (var i = sTable.length - 1; i >= 0 && sTable[i] !== key; --i);
    return i;
}

console.log(sequentialSearch([1, 2, 3, 4, 5], 6));  // -1


上面代码使用倒序查找,这样会稍微快点。尽管如此,但顺序查找最坏情况的比较次数还是n。
于是就衍生了其它优化顺序查找的方法。



折半查找(Binary Search)
折半查找又称为二分查找,是一种效率较高的查找方法。但它有个必要的前提,就是查找表中的所有记录是按关键字有序(升序或降序) 。 折半查找过程中,先确定待查找记录在表中的范围,然后逐步缩小范围(每次将待查记录所在区间缩小一半),直到找到或找不到记录为止。

 1  查找思想
 用Low、High和Mid表示待查找区间的下界、上界和中间位置指针,初值为Low=0,High=n - 1。
 ⑴  取中间位置Mid:Mid=Math.floor((Low+High)/2);
 ⑵  比较中间位置记录的关键字与给定的K值:
     ①  相等: 查找成功;
     ②  大于:待查记录在区间的前半段,修改上界指针: High=Mid-1,转⑴ ;
     ③  小于:待查记录在区间的后半段,修改下界指针:Low=Mid+1,转⑴ ;
 直到越界(Low>High),查找失败。

下面是在一个排好序的数组中成功查找21的示例: enter image description here

下面是一个查找不成功的示例: enter image description here

2  算法分析
 ①  查找时每经过一次比较,查找范围就缩小一半,该过程可用一棵二叉树表示:
     ◆ 根结点就是第一次进行比较的中间位置的记录;
     ◆ 排在中间位置前面的作为左子树的结点;
     ◆ 排在中间位置后面的作为右子树的结点;
     对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。
 ②  将二叉判定树的第Math.floor(Math.log(2, n))+1层上的结点补齐就成为一棵满二叉树,深度不变,h= Math.floor(Math.log(2, n + 1)) 。
 ③  由满二叉树性质知,第i 层上的结点数为Math.pow(2, i-1)(i<=h) ,设表中每个记录的查找概率相等,即Pi=1/n,查找成功时的平均查找长度ASL:
     (n+1)/n*Math.log(2,n+1)-1
 当n很大 (n>50)时, ASL≈ Math.log(2,n+1)-1。


3 算法实现

// 非递归式
function binarySearch(sTable, key) {
    var low = 0;
    var high = sTable.length - 1;

    while (low <= high) {
        var mid = (low + high) >> 1;
        var elem = sTable[mid];

        if (key === elem) return mid;
        else if (key < elem) high = mid - 1;
        else low = mid + 1;
    }

    return -1;
}

console.log('binarySearch: ');
console.log(binarySearch([1, 2, 3, 4, 5], 1));  // 0

// 递归式
function binarySearchRecursive(sTable, key, low, high) {
    if(low == null) low = 0;
    if(high == null) high = sTable.length - 1;
    if (low > high) return -1;

    var mid = (low + high) >> 1;

    if (sTable[mid] === key)
        return mid;
    else if (sTable[mid] > key)
        return binarySearchRecursive(sTable, key, low, mid - 1);
    else
        return binarySearchRecursive(sTable, mid + 1, high);
}

console.log('binarySearchRecursive: ');
console.log(binarySearchRecursive([1, 2, 3, 4, 5], 1)); // 0
console.log(binarySearchRecursive([1, 2, 3, 4, 5], 6)); // -1



Fibonacci查找
 Fibonacci查找方法是根据Fibonacci数列的特点对查找表进行分割。Fibonacci数列的定义是:
     F(0)=0,F(1)=1,F(j)=F(j-1)+F(j-2) 。

1  查找思想
 设查找表中的记录数比某个Fibonacci数小1,即设n=F(j)-1。用Low、High和Mid表示待查找区间的下界、上界和分割位置,初值为Low=0,High=n - 1。
 ⑴   取分割位置Mid:Mid=F(j-1) ;
 ⑵   比较分割位置记录的关键字与给定的K值:
     ① 相等: 查找成功;
     ②  大于:待查记录在区间的前半段(区间长度为F(j-1)-1),修改上界指针: High=Mid-1,转⑴ ;
     ③  小于:待查记录在区间的后半段(区间长度为F(j-2)-1),修改下界指针:Low=Mid+1,转⑴ ;直到越界(Low>High),查找失败。

2  算法实现
 在算法实现时,为了避免频繁计算Fibonacci数,可用两个变量f1和f2保存当前相邻的两个Fibonacci数,这样在以后的计算中可以依次递推计算出。

function fib(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    var f;
    var f0 = 0;
    var f1 = 1;
    for (var i = 2; i <= n; ++i) {
        f = f0 + f1;
        f0 = f1;
        f1 = f;
    }
    return f;
}

/**
 * 在有序表ST中用Fibonacci方法查找关键字为key的记录
 * @param sTable
 * @param key
 * @param n
 */
function fibonacciSearch(sTable, key, n) {
    n = n || sTable.length;
    var low = 0;
    var high = n - 1;
    var f1 = fib(n);
    var f2 = fib(n - 1);

    while (low <= high) {
        var mid = low + f1 - 1;
        if (sTable[mid] === key) return mid;
        else if (key < sTable[mid]) {
            high = mid - 1;
            f2 = f1 - f2;
            f1 = f1 - f2;
        } else {
            low = mid + 1;
            f1 = f1 - f2;
            f2 = f2 - f1;
        }
    }
    return -1;
}

console.log('fibonacciSearch: ');
console.log(fibonacciSearch([1, 2, 3, 4, 5], 5)); // 4
console.log(fibonacciSearch([1, 2, 3, 4, 5], 6)); // -1


 3  算法分析 
 由算法知,Fibonacci查找在最坏情况下性能比折半查找差,但平均性能比折半查找好,而且Fibonacci查找的优点是分割时只需进行加、减运算。



上面介绍的几种静态查找方式都是在每个记录概率相同的情况下,但如果是概率不相同的情况呢?
假设有序表中含有5个记录,并且已知各记录的查找概率不等,分别为p1=0.1,p2=0.2,p3=0.1,p4=0.4,p5=0.2,对此有序表进行折半查找,查找成功时的平均查找长度为:
    ASL = 0.1*2+0.2*3+0.1*1+0.4*2+0.2*3=2.3
但是如果在查找时令给定值先和第4个记录的关键字进行比较,比较不相等时再继续在左子序列或右子序列中进行折半查找,则查找成的平均查找长度为
    ASL = 0.1*3+0.2*2+0.1*3+0.4*1+0.2*2=1.8

这就说明了,当在有序表中个记录查找概率不相等时,使用折半查找的性能未必最优。
查找效率最高即平均查找长度最小,我们可以给出有序表在非等概率情况下构造的判定树应遵循的两个原则:
     1、最先访问的结点应是访问概率最大的结点;
     2、每次访问应使结点两边尚未访问的结点的被访概率之和尽可能相等。

 这两个原则可用一句话来表示,即判定树为带权内路径长度之和最小的二叉树,亦即:PH = ∑wihi  最小,其中 n 为有序表长度,hi 为第 i 个结点在判定树上的层次数,wi = cpi,c 为某个常数,pi 为第 i 个结点的查找概率。

这样的树称为静态最优查找树(static optimal search tree),构造这样一棵树的时间代价太大,亦即时间复杂度很大,这里讲的是构造次优查找树(nearly optimal search tree),构造它的时间代价远远低于构造最优查找树,但查找性能只比最优查找树差1%~2%,很少差3%以上。

设有序表每个记录的权值为 wl,wl+1,…,wh,第一个应访问的结点号为 i ,则有:
    Δpi =   ∑wj - ∑wj   最小,即 Δpi = Min {Δpj } 
再分别对 {rl,rl+1,…,ri-1} 和 {ri+1,ri+2,…,rh} 分别构造次优查找树。 

为便于计算,引入累计权值swi=∑wj,并设wl-1=swl-1=0,则:

enter image description here

于在构造次优查找树时没有考虑前面说的原则一,因此被选为根的结点的权值可能比其邻近结点的权值小,此时应对查找树作适当的调整,将相邻权值大的结点作为根结点。

次优查找树的查找方法与折半查找类似,其平均查找长度与 log n 成正比。

根据前面的算法思路和公式,我们就可以实现静态次优查找树的代码了:


var BinaryTree = require('../Binary tree/BinaryTree').BinaryTree;

/**
 * 由有序表sTable[low..high]及其累计权值表weights递归构造次优查找树
 * @param {BinaryTree} tree
 * @param {Array} sTable
 * @param {Array} sWeights
 * @param {Number} low
 * @param {Number} high
 */
function secondOptimal(tree, sTable, sWeights, low, high) {
    var i = low;
    var min = Math.abs(sWeights[high] - sWeights[low]);
    var dw = sWeights[high] + (sWeights[low - 1] || 0);

    // 选择最小的△Pi值
    for (var j = low + 1; j <= high; ++j) {
        var t = Math.abs(dw - sWeights[j] - sWeights[j - 1]);
        if (t < min) {
            i = j;
            min = t;
        }
    }

    // 调整树根权,选择邻近权值较大的关键字
    var a = 0, b, c = 0;
    if (i - 1 >= low)  b = sWeights[i] - sWeights[i - 1];
    if (i - 2 >= low) a = sWeights[i - 1] - sWeights[i - 2];
    if (i + 1 < high) c = sWeights[i + 1] - sWeights[i];
    if (typeof b === 'number') {
        if (a > c && a > b) --i;
        else if (a < c && c > b)  ++i;
    }

    tree.data = sTable[i];
    //左子树
    if (i === low) tree.leftChild = null;
    else {
        tree.leftChild = new BinaryTree();
        secondOptimal(tree.leftChild, sTable, sWeights, low, i - 1);
    }
    // 右子树
    if (i === high) tree.rightChild = null;
    else {
        tree.rightChild = new BinaryTree();
        secondOptimal(tree.rightChild, sTable, sWeights, i + 1, high);
    }
}

var tree = new BinaryTree();
secondOptimal(tree, ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'], [1, 2, 4, 9, 12, 16, 20, 23, 28], 0, 8);
console.log(tree);


/**
 * 由有序表构造一棵次优查找树
 * @param {Object} obj 有序表,数据元素含有权域weight
 */
function createSOSTree(obj) {
    var tree;
    if (obj.elems.length === 0) tree = null;
    else {
        // 求累计权值表
        var sw = findSW(obj.weights);
        tree = new BinaryTree();
        secondOptimal(tree, obj.elems, sw, 0, obj.elems.length - 1);
    }

    return tree;
}

function findSW(sTable) {
    var sw = [sTable[0]];

    for (var i = 1; i < sTable.length; ++i) {
        sw[i] = sw[i - 1] + sTable[i];
    }

    return sw;
}

var sosTree = createSOSTree({
    elems: ['A', 'B', 'C', 'D', 'E'],
    weights: [1, 30, 2, 29, 3]
});
sosTree.inOrderRecursive(function (value) {
    console.log('inOrder: ' + value);
});

输出:
inOrder: A
inOrder: B
inOrder: C
inOrder: D
inOrder: E

enter image description here

上面的示例和上图是一个根的权小于子树根权的情况
    (a)为调整之前的次优查找树
    (b)为调整之后的次优查找树

这里留个坑,有关最有查找树以后有空再补回来。

相关资料 https://github.com/LukeLin/data-structure-with-js/tree/master/Search

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

友情链接 大搜车前端团队博客
我的收藏