0%

查找算法

查找算法说明

查找定义

根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

查找算法分类:

  1. 静态查找和动态查找

    注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

  2. 无序查找和有序查找

    无序查找:被查找数列有序无序均可

    有序查找:被查找数列必须为有序数列

平均查找长度(Average Search Length,ASL)

需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi * Ci 的和。

  • Pi:查找表中第i个数据元素的概率。
  • Ci:找到第i个数据元素时已经比较过的次数。

顺序查找(Sequence Search)

基本思想

顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。顺序查找适合于存储结构为顺序存储链接存储的线性表。

复杂度分析 

查找成功时的平均查找长度为(假设每个数据元素的概率相等): ASL = (1+2+3+…+n)/n = (n+1)/2

当查找不成功时,需要n+1次比较,时间复杂度为O(n),所以,顺序查找的时间复杂度为O(n)。

代码实现

1
2
3
4
5
6
7
public static int SequenceSearch(int[] a, int value){
int len = a.length;
for(int i = 0; i < len; i++){
if(a[i] == value) return i;
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
public static int SequenceSearch(int[] a, int key) {
int index = a.length - 1;
//如果最后一个数是要找的,直接返回
if (key == a[index])
return index;
//将最后一个数设置为哨兵
a[index] = key;
int i = 0;
while (a[i++] != key);
//若i == index + 1,说明没有查到,返回-1
return i == index + 1 ? -1 : i - 1;
}

二分查找(Binary Search)

基本思想

  1. 从已经排好序的数组或区间中取出中间位置的元素,判断该元素是否满足要搜索的条件,如果满足,停止搜索,程序结束。
  2. 如果正中间的元素不满足条件,则从它两边的区域进行搜索。由于数组是排好序的,可以利用排除法,确定接下来应该从这两个区间中的哪一个去搜索。
  3. 通过判断,如果发现真正要找的元素在左半区间的话,就继续在左半区间里进行二分搜索。反之,就在右半区间里进行二分搜索。

核心步骤:

  1. 确定搜索的范围和区间
  2. 取中间的数判断是否满足条件
  3. 如果不满足条件,判定应该往哪个半边继续进行搜索

时间复杂度分析:

假设我们要对长度为 n 的数组进行二分搜索,T(n) 是执行时间函数,我们可以得到:
$$
T(n) = T(n/2) + 1
$$
代入公式法得:a = 1,b = 2,f(n) = 1,因此:O(nlog(b)a) = O(n0) = 1 等于 O(f(n)),时间复杂度就是 O(nlog(b)alogn) = O(logn)。非常高效。因此也称为对数搜索,但要求待查找的数组或者区间是排好序的。

代码实现

递归解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int binarySearch(int[] nums, int target, int low, int high) {
// 为了避免无限循环,先判断,如果起点位置大于终点位置,表明这是一个非法的区间
if (low > high) {
return -1;
}
// 取正中间那个数的下标 middle。
int middle = low + (high - low) / 2;
// 判断一下正中间的那个数是不是要找的目标数 target,是,就返回下标 middle。
if (nums[middle] == target) {
return middle;
}
// 如果发现目标数在左边,就递归地从左半边进行二分搜索。
// 否则从右半边递归地进行二分搜索
if (target < nums[middle]) {
return binarySearch(nums, target, low, middle - 1);
} else {
return binarySearch(nums, target, middle + 1, high);
}
}
  • 在计算 middle 下标的时候,不能简单地用 (low + hight) / 2,可能会导致溢出
  • 在取左半边以及右半边的区间时,左半边是 [low, middle - 1],右半边是 [middle + 1, high],这是两个闭区间。因为已经确定了 middle 那个点不是我们要找的,就没有必要再把它加入到左、右半边了。
  • 对于一个长度为奇数的数组,例如:{1, 2, 3, 4, 5},按照 low + (high - low) / 2 来计算,middle 就是正中间的那个位置,对于一个长度为偶数的数组,例如 {1, 2, 3, 4},middle 就是正中间靠左边的一个位置。

非递归解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int binarySearch(int[] nums, int target, int low, int high) {
// 在 while 循环里,判断搜索的区间范围是否有效
while (low <= high) {
// 计算正中间的数的下标
int middle = low + (high - low) / 2;
// 判断正中间的那个数是不是要找的目标数 target。如果是,就返回下标 middle
if (nums[middle] == target) {
return middle;
}
// 如果发现目标数在左边,调整搜索区间的终点为 middle - 1;
//否则,调整搜索区间的起点为 middle + 1
if (target < nums[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
// 如果超出了搜索区间,表明无法找到目标数,返回 -1
return -1;
}

插值查找(Insert Search)

基本思想

  • 差值查找算法是对二分查找(折半查找)的一个优化
  • 二分查找算法选取的是中间位置:mid = (low + high)/2
  • 插值查找算法选取的是自适应mid位置开始查找: mid= low + (key - a[low])(high - low)/(a[high] - a[low])

使用场景

  • 插值查找算法通过上面计算的mid,可以判断要查找的位置大概在哪里,对于表较长,且关键字分布比较均匀时候,查找比较快。
  • 关键字分布不均匀的情况下,该方法不一定比折半查找要好

时间复杂度分析

如果元素均匀分布,则O(log2n),在最坏的情况下可能需要 O(n)。

代码实现

递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int insertSearch(int[] nums, int target, int low, int high) {
// 为了避免无限循环,先判断,如果起点位置大于终点位置,表明这是一个非法的区间
if (low > high) {
return -1;
}

// 二分查找
//int middle = low + (high - low) / 2;
// 插值查找
int middle = low + (high - low)*(target - nums[low])/(nums[high] - nums[low]);

// 判断一下是不是要找的目标数 target,是,就返回下标 middle。
if (nums[middle] == target) {
return middle;
}
// 如果发现目标数在左边,就递归地从左半边进行插值查找
// 否则从右半边递归地进行插值查找
if (target < nums[middle]) {
return insertSearch(nums, target, low, middle - 1);
} else {
return insertSearch(nums, target, middle + 1, high);
}
}

非递归解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int binarySearch(int[] nums, int target, int low, int high) {
// 在 while 循环里,判断搜索的区间范围是否有效
while (low <= high) {
// 二分查找
//int middle = low + (high - low) / 2;
// 插值查找
int middle = low + (high - low)*(target - nums[low])/(nums[high] - nums[low]);
// 判断一下是不是要找的目标数 target,是,就返回下标 middle
if (nums[middle] == target) {
return middle;
}
// 如果发现目标数在左边,调整搜索区间的终点为 middle - 1;
//否则,调整搜索区间的起点为 middle + 1
if (target < nums[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
// 如果超出了搜索区间,表明无法找到目标数,返回 -1
return -1;
}