共计 4359 个字符，预计需要花费 11 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
ps：本篇文章写线性查找算法、二分查找算法和插值查找算法。
1、线性查找算法
线性查找算法是最简略的查找算法，它的思路就是：对一组有序或者无序的序列进行遍历，一一比拟，如果要查找的值和序列中的某个值相等，那么证实曾经找到，就返回这个值在序列中的索引；如果要查找的值遍历完序列后还是没有一个与之相等的值，那么就返回 -1。
咱们来举个例子，假如有一个 int 类型数组 a={2,4,3,5,1,8,9}，咱们从这个数组 a 中找 1 和 0，那么代码如下所示：
public class Test8 {
/**
- @param args
*/
public static void main(String[] args) {
int[] a = {2,4,3,5,1,8,9};
int result = linearSearch(a,1);
int result2 = linearSearch(a,0);
System.out.println(result == -1 ? “ 没有找到 1 ” : (“1 在数组 a 中的地位为：” + result));
System.out.println(result2 == -1 ? “ 没有找到 0 ” : (“0 在数组 a 中的地位为：” + result2));
}
/**
- @param arr 要查找的数组
- @param findVal 要查找的值
-
@return 返回对应值在数组中的下标，如果没有返回 -1
*/
public static int linearSearch(int[] arr, int findVal) {
int result = -1;
if (arr == null || arr.length <= 0) {
result = -1;
} else {
for (int i = 0; i < arr.length; i++) {if (arr[i] == findVal) { result = i; break; }}
}
return result;
}
}
运行后果如下所示：
1 在数组 a 中的地位为：4
没有找到 0
2、二分查找算法
二分查找算法又叫折半查找算法，可能进行二分查找算法是有要求的：它是一个有序数列且寄存是依照从小到大进行的。
咱们用 start 示意数列起始地位下标，用 end 示意数列终止地位下标，mid 示意数列两头地位下标，用 findVal 示意待查找元素，用 a 示意数组名称；在曾经排好序的序列中，通过 mid=(start+end)/2 计算出两头地位，通过 findVal 与 mid 进行比拟，如果相等，那么就证实曾经找到；如果 findVal 比 a[mid] 小，那么将 end = mid -1，也就是将 end 挪动到 mid 右边一个地位，并且从新计算 mid；如果比 a[mid] 大，那么将 start = mid + 1，也就是将 start 挪动到 mid 左边一个地位，并且从新计算 mid；始终循环查找，直到 start > end，证实没找到对应的元素，进行循环。
咱们举个例子再详细分析一下，假如我有一个有序数列且大小都是从小到大排列的数组 a={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}，一开始 start = 0，end = 9，mid = (start + end) / 2 = (0 + 9) / 2 = 4，a[mid] = a[4] = 5。
2、1 假如查找 4
（1）因为 4 < a[mid] = a[4] = 5，所以将 end 挪动到 mid 右边一个地位，end = mid – 1 = 4 – 1 = 3。
（2）从新计算 mid，mid =（start + end）/ 2 = (0 + 3) / 2 = 1；因为 4 > a[mid] = a[1] = 2，所以将 start 挪动到 mid 左边一个地位，start = mid + 1 = 1 + 1 = 2。
（3）从新计算 mid，mid =（start + end）/ 2 = (2 + 3) / 2 = 2；因为 4 > a[mid] = a[2] = 3，所以将 start 挪动到 mid 左边一个地位，start = mid + 1 = 2 + 1 = 3。
（4）从新计算 mid，mid =（start + end）/ 2 = (3 + 3) / 2 = 3；因为 4 = a[mid] = a[3] = 4，所以曾经找到，退出循环。
2、2 假如查找 11
（1）因为 11 > a[mid] = a[4] = 5，所以将 start 挪动到 mid 左边一个地位，start = mid + 1 = 4 + 1 = 5。
（2）从新计算 mid，mid =（start + end）/ 2 = (5 + 9) / 2 = 7；因为 11 > a[mid] = a[7] = 8，所以将 start 挪动到 mid 左边一个地位，start = mid + 1 = 7 + 1 = 8。
（3）从新计算 mid，mid =（start + end）/ 2 = (8 + 9) / 2 = 8；因为 11 > a[mid] = a[8] = 9，所以将 start 挪动到 mid 左边一个地位，start = mid + 1 = 8 + 1 = 9。
（4）从新计算 mid，mid =（start + end）/ 2 = (9 + 9) / 2 = 9；因为 11 > a[mid] = a[9] = 10，所以将 start 挪动到 mid 左边一个地位，start = mid + 1 = 9 + 1 = 10。
（5）start = 10，end = 9，start > end，阐明没有找到，所以退出循环。
咱们用代码实现一下：
public class Test8 {
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
binarySearch(a, 4);
binarySearch(a, 11);}
private static int binarySearch(int[] a, int findValue) {
int result = -1;
if (a != null && a.length > 0) {
int mid = 0;
int start = 0;
int end = a.length - 1;
while (true) {mid = (start + end) / 2;
if (start > end) {System.out.println("未从数组 a 中找到" + findValue);
break;
} else if (findValue > a[mid]) {start = mid + 1;} else if (findValue < a[mid]) {end = mid - 1;} else {
result = mid;
System.out.println("从数组 a 中曾经找到了" + findValue + ", 它在第"
+ result + "个地位");
break;
}
}
} else {System.out.println("数组 a 为空或者没有一个数据");
}
return result;}
}
程序运行后，日志打印如下所示
从数组 a 中曾经找到了 4, 它在第 3 个地位
未从数组 a 中找到 11
3、插值查找算法
插值查找算法相似二分查找算法，它查找的数列必须是一个有序数列且寄存是依照从小到大进行的。
咱们用 start 示意数列起始地位的下标，用 end 示意数列终止地位的下标，findValue 示意要查找的数，用 arr 示意数组的名称，mid 示意 start 和 end 闭区间的一个数，它有可能是两头数，也有可能不是；对于插值查找算法，mid 的计算公式为：
int mid = start + (end – start) * (findValue – arr[start]) / (arr[end] – arr[start])
在曾经排好序的序列中，先判断 arr[0] > findValue 又或者 findValue > arr[arr.length – 1] 这 2 个条件是否成立，如果不成立再计算 mid 并通过 findValue 与 mid 进行比拟，如果相等，那么就证实曾经找到，就退出循环；如果 findValue 比 arr[mid] 小，那么将 end = mid -1，也就是将 end 挪动到 mid 右边一个地位，并且从新计算 mid；如果比 arr[mid] 大，那么将 start = mid + 1，也就是将 start 挪动到 mid 左边一个地位，并且从新计算 mid；始终循环查找，直到 start > end，证实没找到对应的元素，进行循环。
咱们举个例子再详细分析一下，假如我有一个数组 arr = {2, 12, 22, 32, 42, 52, 62, 72, 82, 92}，一开始 start = 0，end = 9。
3、1 假如查找 82
（1）arr[0] > findValue 又或者 findValue > arr[arr.length – 1] 这 2 个条件没有一个成立，那么计算 mid，mid=start + (end – start) (findValue – arr[start]) / (arr[end] – arr[start])= 0 + (9 – 0) (82 -2) / (92 – 2) = 8。
（2）做比拟，mid = 8，findValue = arr[8] = 82，侧面 2 曾经找到，退出循环。
3、2 假如查找 102
（1）findValue > arr[arr.length – 1] = arr[9] = 92，所以证实没有找到，完结查找。
咱们用代码实现一下：
public class Test8 {
public static void main(String[] args) {
int[] arr = { 2, 12, 22, 32, 42, 52, 62, 72, 82, 92};
insertSearch(arr, 82);
insertSearch(arr, 102);}
public static int insertSearch(int[] arr, int findValue) {
int result = -1;
if (arr != null && arr.length > 0) {if (findValue < arr[0] || findValue > arr[arr.length - 1]) {System.out.println("在 arr 数组中没有找到" + findValue);
} else {
int start = 0;
int end = arr.length - 1;
int mid = 0;
int count = 0;
while (true) {
count++;
System.out.println("第" + count + "次查找");
mid = start + (end - start) * (findValue - arr[start])
/ (arr[end] - arr[start]);
if (start > end) {System.out.println("在 arr 数组中没有找到" + findValue);
break;
} else if (findValue > arr[mid]) {start = mid + 1;} else if (findValue < arr[mid]) {end = mid - 1;} else {
result = mid;
System.out.println("在 arr 数组中曾经找到了" + findValue + "，它在第"
+ mid + "个地位");
break;
}
}
}
} else {System.out.println("arr 数组为空或者元素个数为 0");
}
return result;}
}
运行程序，日志打印如下所示：
第 1 次查找
在 arr 数组中曾经找到了 82，它在第 8 个地位
在 arr 数组中没有找到 102
