跳到主要内容

查找算法

顺序查找

将待查找的关键字为 key 的元素从头到尾与表中元素进行比较，如果中间存在关键字为 key 的元素，则返回成功；否则，则查找失败。

平均查找长度为 (n+1)/2，时间复杂度为 O(n)。

折半查找

只适用于待查找序列中的元素是有序排列的情况。

设查找表的元素存储在一维数组r[1...n]中，在表中元素已经按照关键字递增（或递减）方式排序的情况下，进行折半查找的方法是：

首先将待查找元素的关键字（key）值与表 r 中间位置上（下标为 mid ）记录的关键字进行比较，若相等，则查找成功。
若 key > r[mid] ,则说明待查记录只可能在后半个子表 r[mid+1...n] 中，下一步应在后半个子表中查找；
若 key < r[mid], 则说明待查记录之可能在前半个子表 r[1...mid-1] 中，，下一步应该在前半个子表中查找；
重复以上步骤，逐步缩小范围，直到查找成功或子表为空时为止。

要注意两点：中间值位置求出若为小数，应该向下取整；中间值已经比较过不相等，在划分下一次比较区间时，无需将中间值位置再纳入下一次比较区间。

折半查找的时间复杂度为 O(log2n)

/**
* 二分查找
*/
public static int binarySearch(int[] arr, int key) {
   int low = 0;
   int high = arr.length - 1;
   while (low <= high) {
//     int mid = (low + high) / 2;
       int mid = low+ (high-low)/2;
       if (arr[mid] == key) {
           return mid;
       }else if (arr[mid] < key) {
           low = mid + 1;
       }else {
           high = mid - 1;
       }
   }
   return -1;
}

哈希查找

哈希表通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址，所以再哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。

例如，设关键码序列为 47,34,13,12,52,38,33,27,3 , 哈希表长度为 11，哈希函数为 Hash(key)= key mod 11 ,则

Hash(47) = 47 mod 11 = 3
Hash(34) = 34 mod 11 = 1
Hash(13) = 13 mod 11 = 2
Hash(12) = 12 mod 11 = 1
Hash(52) = 52 mod 11 = 8
Hash(38) = 38 mod 11 = 5
Hash(33) = 33 mod 11 = 0
Hash(27) = 27 mod 11 = 5
Hash(3) = 3 mod 11 = 3

使用线性探测法解决冲突构造的哈希表如下。

哈希冲突解决方法

开放定址法：Hi=(H(key)+di) % m i=1,2,...k(k<=m-1)
链地址法：它在查找表的每一个记录中增加一个链域，链域中存放

顺序查找
折半查找
哈希查找
- 哈希冲突解决方法