07 查找

moye Lv6
  2024-07-22 17:18:02 2024-07-22 17:18:02 创建   2025-12-11 14:39:48 2025-12-11 14:39:48 更新      

常用搜索算法详解

1. 顺序（线性）搜索

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

1
2
3
4
5
def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**  
 * 找到一个满足条件的值就返回  
 *  
 * @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 代码实现二分（折半）搜索

1
2
3
4
5
6
7
8
9
10
11
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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 代码实现插值搜索

1
2
3
4
5
6
7
8
9
10
11
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 代码实现斐波那契搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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;  
    }  
}
  • 标题: 07 查找
  • 作者: moye
  • 创建于 : 2024-07-22 17:18:02
  • 更新于 : 2025-12-11 14:39:48
  • 链接: https://www.kanes.top/2024/07/22/07 查找/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
07 查找
  1. 1. 常用搜索算法详解
    1. 1.1. 1. 顺序（线性）搜索
    2. 1.2. 2. 二分（折半）搜索
      1. 1.2.1. 2.1 二分（折半）搜索思路分析
      2. 1.2.2. 2.2 代码实现二分（折半）搜索
    3. 1.3. 3. 插值搜索
      1. 1.3.1. 3.1 插值搜索介绍
      2. 1.3.2. 3.2 插值搜索步骤
      3. 1.3.3. 3.3 代码实现插值搜索
    4. 1.4. 4. 斐波那契搜索
      1. 1.4.1. 4.1 介绍
      2. 1.4.2. 4. 2 斐波那契搜索原理
      3. 1.4.3. 4. 3 斐波那契搜索步骤
      4. 1.4.4. 4. 4 代码实现斐波那契搜索