查找

Posted on | In | | Visitors

查找算法分为动态查找和静态查找两种，动态查找主要是B树，AVL树，红黑树等（比较复杂这里就不做介绍）；静态查找表主要就是查找数组（还有一个是hash查找），这里介绍一下常用的静态查找算法。

动态查找与静态查找的不同处在于动态查找的表是在查找过程中动态生成的。

顺序查找

这既是最常用的查找，是针对无序表的查找方法，即将待查找的数表中的数逐个比较。时间复杂度：O(n)。平均查找长度：（n+1）/2

折半查找

针对有序表的查找方法，将表逐次二分，取中间值与待查找值比较，决定查找哪一半。时间复杂度：O(logn)。分割点：mid=(low+high)/2。平均查找长度：log2N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Search(int[] array, int e){
  low = 1;
  high = array.length;
  while(low <= high){
    mid = (low + high) / 2;
    if(e == array[mid]){
      return mid;      //找到查找元素
    }
    else if (e < array[mid]){
      high = mid - 1;        //继续在前半区查找
    }
    else {
      low = mid + 1;         //继续在后半区查找
    }
  }
  return 0;   //顺序表中不存在待查找元素
}

插值查找

所查表是有序表且分布均匀。通过插值方法计算出待查找值在表中的几分之几处，通过与该值比较，缩小查找范围。分割点：mid = low + (key - a[low] / (a[high] - a[low]) * (high - low))。平均查找长度：log2N

斐波那契查找

针对有序表的查找方法，要求表的个数是相应斐波那契数列的个数减1,如果不符，则扩充为符合。分割点：mid = low + f[k-1] -1。平均查找长度：log2N

总结

折半查找进行加法与除法运算（mid = (low + high) / 2）,插值查找进行复杂的四则运算( mid = low + (key - a[low] / (a[high] - a[low]) * (high - low)) )，二斐波那契查找只是运用简单家减法运算 (mid = low + f[k-1] -1) ，在海量的数据查找过程中，这种席位的差别会影响最终的查找效率。三种有序表的查找本质上是分割点的选择不同，各有优劣，实际开发可根据数据的特点综合考虑再做决定。

扩展

还有一个查找方法是分块查找（索引顺序查找）。

即将所查表等分成若干个小表。需额外建立一个索引表，包括两项内容：关键字项（该子表中最大值），指针项（子表第一个记录在原表中的位置）。查询时，先确定待查值在那个子表（因为最大关键字是有序的，所以这里可以用折半查找），再在相应子表中查找（用顺序查找）