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

绝地灬酷狼 2023-10-13 23:28 103阅读 0赞

### 查找概论 ###

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

#### 查找分类 ####

查找表按照操作方式来分两大种。

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

### 顺序表查找 ###

顺序查找 (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 + "处");
            }
        }
    }