07 查找

2024 年 7 月 22 日 星期一

07 查找

常用搜索算法详解

1. 顺序(线性)搜索

顺序搜索是一种简单直观的搜索算法,它按顺序逐个检查数组中的元素,直到找到目标元素或遍历整个数组。其时间复杂度为O(n),适用于小型数据集。

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
/**  
 * 找到一个满足条件的值就返回  
 *  
 * @param arr  
 * @param value  
 * @return  
 */public static int seqSearch(int[] arr, int value) {  
    for (int i = 0; i < arr.length; i++) {  
        if (arr[i] == value) {  
            return i;  
        }  
    }  
    return -1;  
}

2. 二分(折半)搜索

[!Note] 前提是有序 二分搜索是一种高效的搜索算法,要求数组必须是有序的。它通过不断将目标值与数组中间元素比较,将搜索范围缩小一半,直到找到目标或范围缩小到空集。其时间复杂度为O(log n)。

2.1 二分(折半)搜索思路分析

  1. 首先确定该数组的中见下标 mid = (left + right)/2
  2. 让需要查找的数findVal与arr[mid]比较 2.1 findVal > arr[mid] ,  说明你要查找的数在mid 的右边, 因此需要递归的向右查找 2.2 findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找 2.3  findVal == arr[mid] 说明找到,就返回

[!TIP] 递归退出的条件:找到就返回;递归完数组仍然未找到,left>right

2.2 代码实现二分(折半)搜索

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
public static int binarySearch(int[] arr, int left, int right, int value) {  
  
    //当递归完数组仍然未找到,left>right  
    if (left>right){  
        return -1;  
    }  
    int mid = (left + right) / 2;  
    int midVal = arr[mid];  
    if (value > midVal) {//向右递归  
        return binarySearch(arr, mid + 1, right, value);  
    } else if (value < midVal) {  
        //向左递归  
        return binarySearch(arr, left, mid - 1, value);  
    } else {  
        return mid;  
    }  
}
package org.example;  
  
import java.util.ArrayList;  
  
public class BinarySearch {  
    public static void main(String[] args) {  
        int[] arr = {-2, -1, -1, -1, 2, 3, 4, 7};  
        int index = binarySearch(arr, 0, arr.length, 1);  
  
        if (index == -1) {  
            System.out.println("没找到");  
        } else {  
            System.out.println("找到了,下标是" + index);  
        }  
  
        ArrayList<Integer> binarySearch2 = binarySearch2(arr, 0, arr.length, -1);  
        System.out.println(binarySearch2);  
  
    }  
  
    /**  
     * @param arr   数组  
     * @param left  左边索引  
     * @param right 右边索引  
     * @param value 要查找的值  
     * @return 查找到就返回下标,否则返回-1  
     */    public static int binarySearch(int[] arr, int left, int right, int value) {  
  
        //当递归完数组仍然未找到,left>right  
        if (left > right) {  
            return -1;  
        }  
        int mid = (left + right) / 2;  
        int midVal = arr[mid];  
        if (value > midVal) {//向右递归  
            return binarySearch(arr, mid + 1, right, value);  
        } else if (value < midVal) {  
            //向左递归  
            return binarySearch(arr, left, mid - 1, value);  
        } else {  
            return mid;  
        }  
    }  
  
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int value) {  
  
        //当递归完数组仍然未找到,left>right  
        if (left > right) {  
            return new ArrayList<Integer>();  
        }  
        int mid = (left + right) / 2;  
        int midVal = arr[mid];  
        if (value > midVal) {//向右递归  
            return binarySearch2(arr, mid + 1, right, value);  
        } else if (value < midVal) {  
            //向左递归  
            return binarySearch2(arr, left, mid - 1, value);  
        } else {  
//            return mid;  
            //找到mid值时,不立刻返回。  
            //先向mid索引值左边扫描,将所有满足的元素下标加入到集合中  
            //先向mid索引值右边扫描,将所有满足的元素下标加入到集合中  
            //返回ArrayList  
            ArrayList<Integer> resIndexList = new ArrayList<>();  
            int temp = mid - 1;  
            while (true) {  
                if (temp < 0 || arr[temp] != value) {  
                    break;  
                }  
                resIndexList.add(temp);  
                temp -= 1;  
            }  
            resIndexList.add(mid);  
  
            temp = mid + 1;  
            while (true) {  
                if (temp > arr.length - 1 || arr[temp] != value) {  
                    break;  
                }  
                resIndexList.add(temp);  
                temp += 1;  
            }  
            return resIndexList;  
        }  
  
    }  
}

3. 插值搜索

3.1 插值搜索介绍

插值搜索是一种改进的二分搜索算法,特别适用于数据分布均匀的有序数组。它通过目标值在数组中的大致位置估计,从而更快地缩小搜索范围。插值搜索的时间复杂度与二分搜索类似,也是O(log n)。

[!TIP] 思路:插值搜索的核心原理是根据目标值在数组中的估计位置,通过插值公式动态调整搜索范围。它假设数据分布较均匀,因此在估计目标位置时更为准确。

3.2 插值搜索步骤

  1. 初始化搜索范围的低位(low)和高位(high)。
  2. 计算当前猜测值(mid)使用插值公式:mid = low + (target - arr[low]) * (high - low) // (arr[high] - arr[low])
  3. 比较arr[mid]与目标值的大小关系。
  4. 根据比较结果更新搜索范围。
  5. 重复以上步骤直到找到目标值或搜索范围为空。

3.3 代码实现插值搜索

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and arr[low] <= target <= arr[high]:
        mid = low + (target - arr[low]) * (high - low) // (arr[high] - arr[low])
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
package org.example;  
  
import java.util.Arrays;  
  
public class InsertValueSearch {  
    public static void main(String[] args) {  
        int[] arr = new int[100];  
  
        for (int i = 0; i < 100; i++) {  
            arr[i] = i + 1;  
        }  
//        System.out.println(Arrays.toString(arr));  
        int index = insertValueSearch(arr, 0, arr.length-1, 78);  
        System.out.println("下标是:" + index);  
    }  
  
    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {  
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {  
            return -1;  
        }  
  
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);  
        int midVal = arr[mid];  
        if (findVal > midVal) {//向右递归  
            return insertValueSearch(arr, mid + 1, right, findVal);  
        } else if (findVal < midVal) {  
            //向左递归  
            return insertValueSearch(arr, left, mid - 1, findVal);  
        } else {  
            return mid;  
        }  
    }  
}

4. 斐波那契搜索

4.1 介绍

斐波那契搜索是一种对有序数组进行搜索的算法,结合了二分搜索和黄金分割的思想。它通过斐波那契数列来确定分割点,从而减少比较次数。其时间复杂度为O(log n)。

4. 2 斐波那契搜索原理

[!Note] 斐波那契搜索的核心原理是通过计算斐波那契数列中的数值,找到大于等于数组长度的最小斐波那契数。然后利用斐波那契数列中的两个相邻值及一个偏移量,在数组中确定分割点,从而缩小搜索范围。

斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,mid=low+F(k-1)-1(F代表斐波那契数列),如下图所示

对F(k-1)-1的理解: 1)由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 。该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1           2)类似的,每一子段也可以用相同的方式分割 3)但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。

4. 3 斐波那契搜索步骤

  1. 计算斐波那契数列,找到大于等于数组长度的最小斐波那契数。
  2. 初始化斐波那契数列的两个相邻值及一个偏移量。
  3. 在数组中确定分割点,根据比较结果更新搜索范围。
  4. 重复以上步骤直到找到目标值或搜索范围为空。

4. 4 代码实现斐波那契搜索

def fibonacci_search(arr, target):
    fib_m_minus_2, fib_m_minus_1 = 0, 1
    fib = fib_m_minus_1 + fib_m_minus_2

    while fib < len(arr):
        fib_m_minus_2, fib_m_minus_1 = fib_m_minus_1, fib
        fib = fib_m_minus_1 + fib_m_minus_2

    offset = -1
    while fib > 1:
        i = min(offset + fib_m_minus_2, len(arr) - 1)

        if arr[i] < target:
            fib = fib_m_minus_1
            fib_m_minus_1 = fib_m_minus_2
            fib_m_minus_2 = fib - fib_m_minus_1
            offset = i

        elif arr[i] > target:
            fib = fib_m_minus_2
            fib_m_minus_1 -= fib_m_minus_2
            fib_m_minus_2 = fib - fib_m_minus_1

        else:
            return i

    if fib_m_minus_1 and arr[offset + 1] == target:
        return offset + 1

    return -1
package org.example;  
  
import java.util.Arrays;  
  
public class FibonacciSearch {  
    public static int maxSize = 20;  
  
    public static void main(String[] args) {  
        int[] arr = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};  
        System.out.println(fibSearch(arr,1));  
    }  
  
    //构建 Fibonacci数列  
    //非递归的方式创建  
    public static int[] fib() {  
        int[] f = new int[maxSize];  
        f[0] = 1;  
        f[1] = 1;  
        for (int i = 2; i < maxSize; i++) {  
            f[i] = f[i - 1] + f[i - 2];  
        }  
        return f;  
    }  
  
    //查找算法  
    public static int fibSearch(int[] arr, int key) {  
        int low = 0;  
        int high = arr.length - 1;  
        int k = 0;//斐波那契分割数值的下标  
        int mid = 0;  
        int f[] = fib();  
  
        //获取斐波那契分割数值的下标  
        while (high > f[k] - 1) {  
            k++;  
        }  
        //f[k]的值可能大于数组的长度,因此需要Arrays类构造一个新的数组,并指向a  
        int[] temp = Arrays.copyOf(arr, f[k]);//不足的部分使用0填充  
        for (int i = high + 1; i < temp.length; i++) {  
            temp[i] = arr[high];  
        }  
        while (low <= high) {  
            mid = low + f[k - 1] - 1;  
            if (key < temp[mid]) {  
                //向前查找  
                high = mid - 1;  
                //1. 全部元素 = 前面元素+ 后面元素  
                //2. f[k] = f[k-1]+f[k-2]  
                // 前面有f[k-1]个元素,所以可以继续拆分f[k-1] = f[k-2]+f[k-3]  
                //即在f[k-1] 的前面继续查找,下次循环的mid = f[k-1-1]-1  
                k--;  
            } else if (key > temp[mid]) {  
                //向后查找  
                low = mid + 1;  
                k -= 2;  
                //1. 全部元素 = 前面元素+ 后面元素  
                //2. f[k] = f[k-1]+f[k-2]  
                // 后面f[k] = f[k-1]+f[k-2]  
                //因为后面有f[k-2],所以继续拆分f[k-1] = f[k-3]+f[k-4]  
            }else {  
                //确定返回值  
                if (mid<=high){  
                    return mid;  
                }else {  
                    return high;  
                }  
            }  
        }  
        return -1;  
    }  
}
  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...