极速查找（1）-算法分析

查找表是由同一类型的数据元素（或记录）构成的集合

查找算法是计算机科学中重要的概念之一，它是指在给定的数据集合中查找目标
元素。查找算法的目标是在最少的比较次数或操作下，快速确定目标元素的存在
或位置。

一种是静态查找表，只做查找操作的查找表。
	主要操作有，查询某个特定的数据元素是否在查找表中。检索某个特定的数
	据元素和各种属性。
一种是动态查找表，在查找过程中同时插入查找表中不存在的数据元素，或者从
查找表中删除已经存在的某个数据元素。
	主要操作有，查找时插入数据元素，查找十删除数据元素。

顺序查找 (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），也被称为二分查找，是一种高效的查找算法。它
适用于已经排序的数据集合，通过将目标元素与数据集合的中间元素进行比较，
可以迅速缩小查找范围。这个过程类似于猜数字游戏中每次猜测的策略，不断地
将搜索范围缩小一半。

1、确定查找范围的起始点和终点，通常为数组的首尾两个索引。
2、计算查找范围的中间点，取中间元素的索引。
3、将目标元素与中间元素进行比较：
	（1）若目标元素等于中间元素，查找成功，返回中间元素的索引。
	（2）若目标元素小于中间元素，说明目标元素在中间元素的左侧，更新终
		点为中间元素的前一个位置。
	（3) 若目标元素大于中间元素，说明目标元素在中间元素的右侧，更新起
		始点为中间元素的后一个位置。
4、重复步骤2和步骤3，直到找到目标元素或起始点大于终点，表示目标元素不
存在。

折半查找的时间复杂度为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 + "处");
        }
    }
}