查找概论
代码语言：javascript复制查找表是由同一类型的数据元素（或记录）构成的集合
查找算法是计算机科学中重要的概念之一，它是指在给定的数据集合中查找目标
元素。查找算法的目标是在最少的比较次数或操作下，快速确定目标元素的存在
或位置。查找分类
查找表按照操作方式来分两大种。
代码语言：javascript复制一种是静态查找表，只做查找操作的查找表。
主要操作有，查询某个特定的数据元素是否在查找表中。检索某个特定的数
据元素和各种属性。
一种是动态查找表，在查找过程中同时插入查找表中不存在的数据元素，或者从
查找表中删除已经存在的某个数据元素。
主要操作有，查找时插入数据元素，查找十删除数据元素。顺序表查找
代码语言：javascript复制顺序查找 (Sequential Search)，也被称为线性查找，是一种简单直观的查找
算法。顺序查找是从数据集合的起始位置开始逐个与目标元素进行比较，直到找
到目标元素或遍历完整个数据集合。顺序查找算法实现
代码语言：javascript复制public class SequentialSearch {
public static int search(int[] arr, int target) {
// 遍历数组中的每个元素
for (int i = 0; i < arr.length; i ) {
// 如果找到目标元素，返回其索引
if (arr[i] == target) {
return i;
}
}
// 若遍历完整个数组都没有找到目标元素，则返回-1表示未找到
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 9, 2, 7, 1};
int target = 7;
int result = search(arr, target);
if (result == -1) {
System.out.println("目标元素未找到");
} else {
System.out.println("目标元素在索引" result "处");
}
}
}运行代码，输出结果为：“目标元素在索引4处”，表示目标元素7在数组的索引4
处。若将target修改为10，运行结果将为：“目标元素未找到”。public class SequentialSearch {
public static int search(int[] arr, int target) {
int n = arr.length;
// 遍历数组中的每个元素
for (int i = 0; i < n; i ) {
// 判断当前元素是否等于目标元素
if (arr[i] == target) {
// 将目标元素与当前元素交换，以提高下次查找时的性能
if (i > 0) {
int temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
return i - 1; // 返回当前元素的索引
}
}
return -1; // 未找到目标元素
}
public static void main(String[] args) {
int[] arr = {5, 3, 9, 2, 7, 1};
int target = 7;
int result = search(arr, target);
if (result == -1) {
System.out.println("目标元素未找到");
} else {
System.out.println("目标元素在索引" result "处");
}
}
}在上述代码中，我们进行了以下优化：
将目标元素与它之前的元素交换位置。通过这种交换，我们可以确保下次查
找时，目标元素就在前面，减少了遍历的次数。这种优化思路适用于在查找
过程中频繁查询相同的元素，希望将这些元素移动到开头以提高下次查询的
效率。
注意
在交换元素位置时，我们需要确保当前元素的索引大于0，以避免越界。返
回值也相应地从i改为i - 1，以反映元素交换后的位置。
但是，如果数据集合较大，并且存在大量重复查询的情况，可能会更适合使用其
他更高效的查找算法。有序表查找
折半查找（二分查找）
代码语言：javascript复制折半查找（Binary Search），也被称为二分查找，是一种高效的查找算法。它
适用于已经排序的数据集合，通过将目标元素与数据集合的中间元素进行比较，
可以迅速缩小查找范围。这个过程类似于猜数字游戏中每次猜测的策略，不断地
将搜索范围缩小一半。步骤
代码语言：javascript复制1、确定查找范围的起始点和终点，通常为数组的首尾两个索引。
2、计算查找范围的中间点，取中间元素的索引。
3、将目标元素与中间元素进行比较：
（1）若目标元素等于中间元素，查找成功，返回中间元素的索引。
（2）若目标元素小于中间元素，说明目标元素在中间元素的左侧，更新终
点为中间元素的前一个位置。
（3) 若目标元素大于中间元素，说明目标元素在中间元素的右侧，更新起
始点为中间元素的后一个位置。
4、重复步骤2和步骤3，直到找到目标元素或起始点大于终点，表示目标元素不
存在。分析
代码语言：javascript复制折半查找的时间复杂度为O(log n)，其中n是数据集合中的元素个数。因为在每
次比较后，查找范围都缩小一半，因此查找所需的比较次数随着数据集合的增长
而以对数方式增加。注意
代码语言：javascript复制折半查找要求数据集合已经按升序或降序排序，以确保查找的正确性。如果数据
集合未排序，需要先进行排序操作，然后才能使用折半查找来定位目标元素的位
置。代码实现
代码语言：javascript复制public class BinarySearch {
public static int search(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low (high - low) / 2;
if (arr[mid] == target) {
return mid; // 找到目标元素，返回索引
} else if (arr[mid] < target) {
low = mid 1; // 目标元素在右侧，更新查找范围为右半部分
} else {
high = mid - 1; // 目标元素在左侧，更新查找范围为左半部分
}
}
return -1; // 目标元素未找到
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 7, 9};
int target = 7;
int result = search(arr, target);
if (result == -1) {
System.out.println("目标元素未找到");
} else {
System.out.println("目标元素在索引" result "处");
}
}
}插值查找
代码语言：javascript复制插值查找（Interpolation Search）是一种改进的查找算法，它在数据集合中
进行查找时，根据目标元素与数据集合中最小值和最大值的相对位置，进行更精
细的插值估计，从而快速缩小查找范围。步骤
代码语言：javascript复制1、确定查找范围的起始点和终点，通常为数组的首尾两个索引。
2、计算目标元素的估计位置：
（1）假设数据集合的最小值为min，最大值为max。
（2）计算目标元素在数据集合中的相对位置：(target - arr[start]) /
(arr[end] - arr[start])，其中target为目标元素的值。
（3）使用上述相对位置乘以查找范围的长度，得到目标元素的估计位置。
（4）转换为整数索引，得到划分点。
3、将目标元素与划分点处的元素进行比较：
（1）若目标元素等于划分点处的元素，查找成功，返回划分点的索引。
（2）若目标元素小于划分点处的元素，说明目标元素在划分点的左侧，更
新终点为划分点的前一个位置。
（3）若目标元素大于划分点处的元素，说明目标元素在划分点的右侧，更
新起始点为划分点的后一个位置。
4、重复步骤2和步骤3，直到找到目标元素或起始点大于终点，表示目标元素不
存在。分析
代码语言：javascript复制插值查找的时间复杂度在平均情况下为O(log log n)，但最坏情况下可能达到
O(n)，其中n是数据集合中的元素个数。插值查找适合于数据集合中分布较为均
匀的情况，对于分布不均或有序性较差的数据集合，插值查找的效果可能变差。注意
代码语言：javascript复制插值查找也要求数据集合已经按升序或降序排序。如果数据集合未排序，需要先
进行排序操作，然后才能使用插值查找来定位目标元素的位置。代码实现
代码语言：javascript复制public class InterpolationSearch {
public static int search(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
int pos = low (((high - low) * (target - arr[low])) / (arr[high] - arr[low]));
if (arr[pos] == target) {
return pos; // 找到目标元素，返回索引
} else if (arr[pos] < target) {
low = pos 1; // 目标元素在右侧，更新查找范围为右半部分
} else {
high = pos - 1; // 目标元素在左侧，更新查找范围为左半部分
}
}
return -1; // 目标元素未找到
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 7, 9};
int target = 7;
int result = search(arr, target);
if (result == -1) {
System.out.println("目标元素未找到");
} else {
System.out.println("目标元素在索引" result "处");
}
}
}斐波那契查找
代码语言：javascript复制斐波那契查找（Fibonacci Search）是一种基于斐波那契数列的查找
算法。它结合了二分查找和插值查找的优点，可以在特定条件下提供更
好的性能。步骤
代码语言：javascript复制1、确定斐波那契数列的长度，使得最小的斐波那契数不小于待查找数
据集合的长度。即找到最小的斐波那契数F[k]，满足F[k] >= n。
2、将数据集合扩展到长度为F[k]，扩展部分使用数据集合最后一个元
素填充。
3、定义两个指针，low和high，初始值分别为0和F[k] - 1。
4、将待查找元素与指针low和high对应的元素进行比较。
（1）若待查找元素等于指针low对应的元素，表示找到了目标元
素，返回low。
（2）若待查找元素大于指针low对应的元素，说明目标元素在右
侧，指针low右移到指针high的位置，指针high右移两位。
（3）若待查找元素小于指针low对应的元素，说明目标元素在左
侧，指针low左移两位，指针high左移一位。
5、重复步骤4，直到找到目标元素，或者指针low大于指针high，表
示目标元素不存在。注意
代码语言：javascript复制斐波那契查找的前提条件是数据集合必须是有序的。与二分查找不同，
斐波那契查找不是将查找范围划分为两部分，而是通过斐波那契数列的
特性来确定待查找元素的位置。代码实现
代码语言：javascript复制public class FibonacciSearch {
public static int search(int[] arr, int target) {
int len = arr.length;
int fib2 = 0; // F[k-2]
int fib1 = 1; // F[k-1]
int fibK = fib2 fib1; // F[k]
while (fibK < len) {
fib2 = fib1;
fib1 = fibK;
fibK = fib2 fib1;
}
int offset = -1; // 偏移量
int low = 0;
while (fibK > 1) {
int index = Math.min(offset fib2, len - 1);
if (arr[index] < target) {
fibK = fib1;
fib1 = fib2;
fib2 = fibK - fib1;
offset = index;
low = index 1;
} else if (arr[index] > target) {
fibK = fib2;
fib1 = fib1 - fib2;
fib2 = fibK - fib1;
} else {
return index; // 找到目标元素，返回索引
}
}
if (fib1 == 1 && arr[low] == target) {
return low; // 找到目标元素，返回索引
}
return -1; // 目标元素未找到
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 7, 9};
int target = 7;
int result = search(arr, target);
if (result == -1) {
System.out.println("目标元素未找到");
} else {
System.out.println("目标元素在索引" result "处");
}
}
}
