静态查找
静态表是只执行查找操作,而不执行插入、删除等操作的表。
现在常说的有五大查找方法:顺序查找、分块查找、索引查找、树查找、哈希查找。
后两种之前写过了二叉查找树和哈希表,现在回顾前面三种,它们都属于顺序表查找。
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.索引查找
索引查找要求将表分成好几块。
块内无序,块间有序。
比如第一块的最大值一定小于第二块,第三块的元素一定大于第二块。
这时候查找就只需要对合适的块进行顺序查找,比较次数根据分的块的数量而定。
(图片来源于网络)