算法 – 静态查找

先明确“查找”的几个定义:

查找

查找表:(同一类型的)数据元素(或记录)构成的集合,是一种灵活的数据结构

静态查找表:只查找,不改变查找表;

动态查找表:需要在查找表中插入元素或删除元素,这类查找表就是动态查找表;

平均查找长度:查找的基本操作是将记录的关键字与给定值进行比较;为确定记录在查找表中的位置,比较次数的期望值称为查找算法在查找成功时的平均查找长度;


静态查找中常用的算法是顺序查找和二分法查找。

顺序查找

基本思路是从表的一端开始,逐个进行比较;对顺序存储方式和链式存储方式的查找表都适用;成功查找的平均次数约为表长的一半;表现在代码中,就是一个for循环

  • 优点:算法简单,适用面广,对查找表的结构没有要求;
  • 缺点:当查找表数据量比较大时,平均查找长度较大,查找效率较低;

JavaScript 实现

var arr = [3, 12, 4, 6, 9, 10, 1, 15];
console.log(find(9, arr));
function find(tar, arr) {
    for (var i = 0, len = arr.length - 1; i < len; i++) {
        if (tar === arr[i]) return i;
    }
    return -1;
}

二分法查找

使用二分法查找有个前提条件:需要查找表按照关键字递增/递减的方式排列;

基本思路:从查找表中间位置将查找表“拆分”为两个子表,通过目标值和中间位置值的大小来决定下一步去哪个子表继续查找,然后对符合的子表重复上面的拆分、比较操作;直到查找成功或子表为空时结束;

JavaScript 实现

var arr = [1, 3, 4, 6, 9, 10, 12, 15];
console.log(halfFind(9, arr));

function halfFind(tar, arr) {
    var low = 0, high = arr.length, mid;
 
    while (low <= high) {
        mid = parseInt((low + high) / 2);
        var midVal = arr[mid];
        if (tar === midVal) return mid;
        else if (tar < midVal) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

mid = parseInt((low + high) / 2)

这一句是取数组的中间下标,JavaScript 中可能会出现小数,所以用 parseInt 转一下,其他强类型语言比如C#中,两个整数相除结果肯定为整数,不需要转型;
数组长度为偶数的时候,中间下标有两个,取哪个都可以,上面这句代码取的是后边的值;

优点:效率比顺序查找要高;

缺点:它要求查找表进行顺序存储并按关键字有序排列,需要插入或删除时,需要移动大量的元素;

适用于表不易变动,又经常查找的情况(静态查找表和变动频率不大的动态查找表);

DEMO

我做了一个二分法查找的动态效果,没有考虑重复数字的情况,只在数组中找第一个出现目标数字的位置;具体点击这里查看;

如果这篇文章对你有用,可以点击下面的按钮告诉我

0

发表回复