查找概论
查找表是由同一类型的数据元素（或记录）构成的集合 查找算法是计算机科学中重要的概念之一，它是指在给定的数据集合中查找目标 元素。查找算法的目标是在最少的比较次数或操作下，快速确定目标元素的存在 或位置。
查找分类
查找表按照操作方式来分两大种。
一种是静态查找表，只做查找操作的查找表。 主要操作有，查询某个特定的数据元素是否在查找表中。检索某个特定的数 据元素和各种属性。 一种是动态查找表，在查找过程中同时插入查找表中不存在的数据元素，或者从 查找表中删除已经存在的某个数据元素。 主要操作有，查找时插入数据元素，查找十删除数据元素。
顺序表查找
顺序查找 (Sequential Search)，也被称为线性查找，是一种简单直观的查找 算法。顺序查找是从数据集合的起始位置开始逐个与目标元素进行比较，直到找 到目标元素或遍历完整个数据集合。
顺序查找算法实现
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，以反映元素交换后的位置。 但是，如果数据集合较大，并且存在大量重复查询的情况，可能会更适合使用其 他更高效的查找算法。
有序表查找
折半查找（二分查找）
折半查找（Binary Search），也被称为二分查找，是一种高效的查找算法。它 适用于已经排序的数据集合，通过将目标元素与数据集合的中间元素进行比较， 可以迅速缩小查找范围。这个过程类似于猜数字游戏中每次猜测的策略，不断地 将搜索范围缩小一半。
分析
折半查找的时间复杂度为O(log n)，其中n是数据集合中的元素个数。因为在每 次比较后，查找范围都缩小一半，因此查找所需的比较次数随着数据集合的增长 而以对数方式增加。
注意
折半查找要求数据集合已经按升序或降序排序，以确保查找的正确性。如果数据 集合未排序，需要先进行排序操作，然后才能使用折半查找来定位目标元素的位 置。
代码实现
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 + "处"); } } }
插值查找
插值查找（Interpolation Search）是一种改进的查找算法，它在数据集合中 进行查找时，根据目标元素与数据集合中最小值和最大值的相对位置，进行更精 细的插值估计，从而快速缩小查找范围。
步骤
1、确定查找范围的起始点和终点，通常为数组的首尾两个索引。 2、计算目标元素的估计位置： （1）假设数据集合的最小值为min，最大值为max。 （2）计算目标元素在数据集合中的相对位置：(target - arr[start]) / (arr[end] - arr[start])，其中target为目标元素的值。 （3）使用上述相对位置乘以查找范围的长度，得到目标元素的估计位置。 （4）转换为整数索引，得到划分点。 3、将目标元素与划分点处的元素进行比较： （1）若目标元素等于划分点处的元素，查找成功，返回划分点的索引。 （2）若目标元素小于划分点处的元素，说明目标元素在划分点的左侧，更 新终点为划分点的前一个位置。 （3）若目标元素大于划分点处的元素，说明目标元素在划分点的右侧，更 新起始点为划分点的后一个位置。 4、重复步骤2和步骤3，直到找到目标元素或起始点大于终点，表示目标元素不 存在。
分析
插值查找的时间复杂度在平均情况下为O(log log n)，但最坏情况下可能达到 O(n)，其中n是数据集合中的元素个数。插值查找适合于数据集合中分布较为均 匀的情况，对于分布不均或有序性较差的数据集合，插值查找的效果可能变差。
注意
插值查找也要求数据集合已经按升序或降序排序。如果数据集合未排序，需要先 进行排序操作，然后才能使用插值查找来定位目标元素的位置。
代码实现
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 + "处"); } } }
斐波那契查找
斐波那契查找（Fibonacci Search）是一种基于斐波那契数列的查找 算法。它结合了二分查找和插值查找的优点，可以在特定条件下提供更 好的性能。
步骤
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，表 示目标元素不存在。
注意
斐波那契查找的前提条件是数据集合必须是有序的。与二分查找不同， 斐波那契查找不是将查找范围划分为两部分，而是通过斐波那契数列的 特性来确定待查找元素的位置。
代码实现
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 + "处"); } } }
