线性查找

介绍

线性查找(Sequential Search)又叫顺序查找,是最基本的查找技术,它的查找过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录;如果直到最后一个(或第一个)记录,其关键字和给定值比较都不等时,则表中没有所查的记录,查找不成功。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.nanzx.search;

public class SeqSearch {

public static void main(String[] args) {
int arr[] = { 1, 9, 11, -1, 34, 89 };
int index = seqSearch(arr, -11);
if (index == -1) {
System.out.println("没有找到。");
} else {
System.out.println("找到,下标为=" + index);
}
}

public static int seqSearch(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
}

二分查找

介绍

二分查找(Binary Search)技术,又称为折半查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。它的查找过程是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

递归实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package com.nanzx.search;

public class BinarySearch {

public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1000, 1234 };
int index = binarySearch(arr, 0, arr.length - 1, 11);
if (index == -1) {
System.out.println("没有找到。");
} else {
System.out.println("找到,下标为=" + index);
}
}

public static int binarySearch(int[] arr, int left, int right, int value) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midValue = arr[mid];
if (value < midValue) {
return binarySearch(arr, left, mid - 1, value);
} else if (value > midValue) {
return binarySearch(arr, mid + 1, right, value);
} else {
return mid;
}
}
}

优化代码,找到所有相同的数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package com.nanzx.search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {

public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1000, 1234 };
List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
System.out.println("resIndexList=" + resIndexList);
}

public static List<Integer> binarySearch(int[] arr, int left, int right, int value) {
if (left > right) {
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;
int midValue = arr[mid];
if (value < midValue) {
return binarySearch2(arr, left, mid - 1, value);
} else if (value > midValue) {
return binarySearch2(arr, mid + 1, right, value);
} else {
List<Integer> resIndexlist = new ArrayList<Integer>();
int temp = mid - 1;//从mid向左遍历查找相同数
while (true) {
if (temp < 0 || arr[temp] != value) {
break;
}
resIndexlist.add(temp);
temp--;
}
resIndexlist.add(mid);
temp = mid + 1;//从mid向右遍历查找相同数
while (true) {
if (temp > arr.length - 1 || arr[temp] != value) {
break;
}
resIndexlist.add(temp);
temp++;
}
return resIndexlist;
}
}
}

非递归实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package com.nanzx.binarysearchnorecursion;

public class BinarySearchNoRecursion {

public static void main(String[] args) {
int[] arr = { 1, 3, 8, 10, 11, 67, 100 };
int index = binarySearch(arr, 100);
System.out.println("index=" + index);
}

public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
}
}
return -1;
}
}

插值查找

介绍

插值查找算法类似于二分查找,也需要记录是有序的,不同的是插值查找每次从自适应mid处开始查找。
将二分查找求中间记录的mid 索引公式改成:

key:要查找的值;low:第一个记录在数组中的索引值;high:最后一个记录在数组中的索引值

(key-a[low]) / (a[high]-a[low])就是查找值在这个均匀分布的有序序列中的大致位置的系数

对应的代码公式为:

int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package com.nanzx.search;

public class InsertValueSearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1234};
int index = insertValueSearch(arr, 0, arr.length - 1, 10);
System.out.println("index = " + index);
}

public static int insertValueSearch(int[] arr, int left, int right, int value) {

System.out.println("插值查找次数~~");

// 注意:value < arr[0] 和 value > arr[arr.length - 1] 必须需要
// 否则我们得到的 mid 可能越界
if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
return -1;
}

// 求出mid, 自适应
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);

int midValue = arr[mid];
if (value > midValue) {
return insertValueSearch(arr, mid + 1, right, value);
} else if (value < midValue) {
return insertValueSearch(arr, left, mid - 1, value);
} else {
return mid;
}
}
}

注意事项

  1. 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快
  2. 关键字分布不均匀的情况下,该方法不一定比折半查找要好