静态查找

静态表是只执行查找操作,而不执行插入、删除等操作的表。

现在常说的有五大查找方法:顺序查找、分块查找、索引查找、树查找、哈希查找。

后两种之前写过了二叉查找树和哈希表,现在回顾前面三种,它们都属于顺序表查找。

1.顺序查找

思路最简单的查找,也就是遍历一遍看看有没有相等的元素。

可以设置一个哨兵,这样全都不相等也可以在哨兵那里返回,不必设边界条件。

int find(T key){
            data[0] =key;//监视哨
            //因为就算前面碰不到匹配的在0这里也会返回0,就不需要特别判断边界条件 
            for(int i=len;i>=0;i--){
                if(data[i]==key)
                    return i;
            }
        } 

2.分块查找

分块查找的对象必须是有序表,以递增序列为例,我们先找到中间的那个元素,若是该元素比key值小,则下一步只需要查找左边的,否则下一步只需要查找右边的。

显然我们可以发现,分块查找的比较次数要小于顺序查找。

    int find_half(T key){

            int low =1;
            int high = len;

            while(low<=high){
                cout<<data[(low+high)/2]<<" "<<key <<endl;
                if(data[(low+high)/2]==key) return (low+high)/2;
                else if(data[(low+high)/2] < key)
                    low = (low+high)/2+1;
                else if(data[(low+high)/2]>key){
                    if((low+high)/2==1) break; //如果已经是最小值还比当前元素大 
                    high = (low+high)/2;
                }
            }
            return 0;
        }

3.索引查找

 索引查找要求将表分成好几块。

块内无序,块间有序。

比如第一块的最大值一定小于第二块,第三块的元素一定大于第二块。

这时候查找就只需要对合适的块进行顺序查找,比较次数根据分的块的数量而定。

 (图片来源于网络)

02-09 19:23