算法：搜索

敖炜 Lv5
  2023-11-29 18:41:50 2023-11-29 18:41:50 创建   2024-04-19 09:30:36 2024-04-19 09:30:36 更新      3.2k 字  13 分钟  

前面把常见的数据结构复习的差不多了，接下来复习一下算法。这一篇要讲的是搜索算法

二分查找

二分查找是一种基于分治策略的高效搜索算法。利用数据的有序性(递增)，每轮减少一半搜索范围，直到找到目标元素或搜索区间为空

问题描述

给定一个长度为n的数组nums，元素从小到大排列，其中不包含重复元素。请查找并返回元素target在该数组中的索引。若数组不包含该元素，则返回-1。

算法思路及实现

初始化两个指针i, j，分别指向数组**首元素(0)和尾元素(n-1)**，代表搜索区间为[0, n-1]。之后，循环执行以下两步

  1. 计算当前搜索区间中点索引，（向下取整）
  2. 判断索引m处元素nums[m]和target的大小关系，进入对应分支
    • nums[m] target：说明target在[m+1, j]中，执行i = m+1
    • nums[m] target：说明target在[i, m-1]中，执行j = m-1
    • nums[m] target：说明找到target，返回索引m

若**搜索区间为空(i>j)**，说明数组不包含目标元素，返回-1

tips: i和j都是int类型，故i+j可能会超出int取值范围，为避免越界，可用m = i+(j-i)/2来计算中点

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(nums, target):
    i, j = 0, len(nums) - 1
    
    while i <= j:
        m = (i + j) // 2
        if nums[m] < target:
            i = m + 1
        elif nums[m] > target:
            j = m - 1
        else:
            return m
    return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(vector<int>& nums, int target){
    int i = 0, j = nums.size() - 1;

    while(i <= j){
        int m = i + (j - i) / 2;
        if(nums[m] < target){
            i = m + 1;
        }else if(nums[m] > target){
            j = m - 1;
        }else{
            return m;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int binarySearch(int *nums, int len, int target) {
    int i = 0, j = len - 1;
    while (i <= j) {
        int m = i + (j - i) / 2;
        if (nums[m] < target)
            i = m + 1;
        else if (nums[m] > target)
            j = m - 1;
        else
            return m;
    }
    return -1;
}

复杂度分析

  • 时间复杂度：二分循环中，区间每轮缩小一半，循环次数最多为，故时间复杂度为

  • 空间复杂度：指针i和j使用常数大小空间，故时间复杂度为

优点与局限性

优点：

  • 时间效率高

  • 无须额外空间，无需额外数据结构

局限性：

  • 仅适用于有序数据，对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为

  • 仅适用于数组，需要对元素进行跳跃式（随机）访问，不适用于链表或基于链表实现的数据结构

  • 数据量较小时，线性查找性能更佳。每一轮循环中，线性查找进行的操作数更少。

二分查找插入点

二分查找还可用于搜索目标元素的插入位置

无重复元素时

给定一个长度为n的有序数组nums和一个元素target，数组不存在重复元素。现将target插入到数组nums中，并保持其有序性。若数组中已存在target，则插入到其左方。请返回插入位置在数组中的索引

二分查找插入点示例数据

  • 当数组中包含target时，插入点的索引就是该target的索引

  • 当数组中不包含target时，二分查找结束后，i指向首个大于target的元素，j指向首个小于target的元素，插入点的索引为i

1
2
3
4
5
6
7
8
9
10
11
def binary_search_insertion_simple(nums, target):
    i, j = 0, len(nums) - 1
    while i <= j:
        m = (i + j) // 2
        if nums[m] < target:
            i = m + 1
        elif nums[m] > target:
            j = m - 1
        else:
            return m
    return i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearchInsertionSimple(vector<int>& nums, int target){
    int i = 0, j = nums.size() - 1;
    while(i <= j){
        int m = i + (j - i) / 2;
        if (nums[m] < target){
            i = m + 1;
        }else if(nums[m] > target){
            j = m - 1;
        }else{
            return m;
        }
    }
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearchInsertionSimple(int *nums, int numSize, int target) {
    int i = 0, j = numSize - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            return m; // 找到 target ，返回插入点 m
        }
    }
    // 未找到 target ，返回插入点 i
    return i;
}

有重复元素时

数组中可能包含重复元素，其余条件不变。

若数组中有多个target，普通二分查找只能返回其中一个target的索引，无法确定该元素的左边和右边有多少target。而我们需要查找数组中最左一个target的索引

  1. 方法一

进行普通二分查找，得到任意一个target的索引，记为k；从k开始，向左进行线性遍历，直到找到最左一个target的索引

线性查找重复元素的插入点

该方法由于包含线性查找，时间复杂度为，效率较低

  1. 方法二

拓展普通二分查找代码，整体流程不变，每轮先计算中点索引m，再判断target和nums[m]的大小关系

  • nums[m] != target时，进行普通二分查找的缩小区间操作
  • nums[m] == target时，小于target的元素在[i, m-1]中，令j=m-1，使j向小于target的元素靠近

循环完成后，i指向最左一个target，j指向首个小于target的元素，索引i就是插入点

1
2
3
4
5
6
7
8
9
10
11
def binary_search_insertion(nums, target):
    i, j = 0, len(nums) - 1
    while i <= j:
        m = (i + j) // 2
        if nums[m] < target:
            i = m + 1
        elif nums[m] > target:
            j = m - 1
        else:
            j = m - 1
    return i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearchInsertion(vector<int> &nums, int target) {
    int i = 0, j = nums.size() - 1;
    while (i <= j) {
        int m = i + (j - i) / 2;
        if (nums[m] < target) {
            i = m + 1;
        } else if (nums[m] > target) {
            j = m - 1;
        } else {
            j = m - 1;
        }
    }
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearchInsertion(int *nums, int numSize, int target) {
    int i = 0, j = numSize - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
        }
    }
    // 返回插入点 i
    return i;
}

二分查找边界

查找左边界

给定一个长度为n的有序数组nums，数组可能包含重复元素。请返回数组中最左一个元素target的索引。若数组中不包含该元素，则返回-1

查找插入点的本质就是在查找最左一个target的索引

数组中不包含target时，有两种可能结果

  • 插入点索引i越界
  • 元素nums[i] != target
1
2
3
4
5
def binary_search_left_edge(nums, target):
    i = binary_search_insertion(nums, target)
    if i == len(nums) or nums[i] != target:
        return -1
    return i
1
2
3
4
5
6
7
int binarySearchLeftEdge(vector<int> &nums, int target) {
    int i = binarySearchInsertion(nums, target);
    if (i == nums.size() || nums[i] != target) {
        return -1;
    }
    return i;
}
1
2
3
4
5
6
7
8
9
10
int binarySearchLeftEdge(int *nums, int numSize, int target) {
    // 等价于查找 target 的插入点
    int i = binarySearchInsertion(nums, numSize, target);
    // 未找到 target ，返回 -1
    if (i == numSize || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

查找右边界

可以替换在nums[m] == target情况下的指针收缩操作。但有更简单的方法

  1. 复用查找左边界

将查找最右一个target转化为查找最左一个target + 1。j指向最右一个target，i-1就得到j

将查找右边界转化为查找左边界

1
2
3
4
5
6
def binary_search_right_edge(nums, target):
    i = binary_search_insertion(nums, target + 1)
    j = i - 1
    if j == -1 or nums[j] != target:
        return -1
    return j
1
2
3
4
5
6
7
8
int binarySearchRightEdge(vector<int> &nums, int target) {
    int i = binarySearchInsertion(nums, target + 1);
    int j = i - 1;
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
int binarySearchRightEdge(int *nums, int numSize, int target) {
    // 转化为查找最左一个 target + 1
    int i = binarySearchInsertion(nums, numSize, target + 1);
    // j 指向最右一个 target ，i 指向首个大于 target 的元素
    int j = i - 1;
    // 未找到 target ，返回 -1
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    // 找到 target ，返回索引 j
    return j;
}
  1. 转化为查找元素

若数组中不包含target，i和j最终会分别指向首个大于、小于target的元素。因此可以构造一个数组中不存在的元素，用于查找左右边界

  • 查找最左一个target：转化为查找target - 0.5，返回指针i
  • 查找最右一个target：转化为查找target + 0.5，返回指针j

将查找边界转化为查找元素

哈希优化策略

问题描述

给定一个整数数组nums和一个目标元素target，请在数组中搜索“和”为target的两个元素，并返回它们的数组索引。返回任意一个解即可

线性查找：以时间换空间

直接遍历所有可能的组合

线性查找求解两数之和

1
2
3
4
5
6
def two_sum_brute_force(nums, target):
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
1
2
3
4
5
6
7
8
9
10
vector<int> twoSumBruteForce(vector<int> &nums, int target) {
    int size = nums.size();
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (nums[i] + nums[j] == target)
                return {i, j};
        }
    }
    return {};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int *res = malloc(sizeof(int) * 2);
                res[0] = i, res[1] = j;
                *returnSize = 2;
                return res;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

时间复杂度为，空间复杂度为

哈希查找：以空间换时间

借助一个哈希表，键为数组元素，值为元素索引。循环遍历数组，每轮判断target - nums[i]是否在哈希表中

  • 若在，则直接返回这两个元素的索引
  • 若不在，将键值对nums[i]和索引i添加进哈希表
1
2
3
4
5
6
7
def two_sum_hash_table(nums, target):
    dic = {}
    for i in range(len(nums)):
        if target - nums[i] in dic:
            return [dic[target - nums[i]], i]
        dic[nums[i]] = i
    return []
1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSumHashTable(vector<int> &nums, int target) {
    int size = nums.size();
    unordered_map<int, int> dic;
    for (int i = 0; i < size; i++) {
        if (dic.find(target - nums[i]) != dic.end()) {
            return {dic[target - nums[i]], i};
        }
        dic.emplace(nums[i], i);
    }
    return {};
}
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
typedef struct{
    int key;
    int value;
    UT_hash_handle hh; // 基于uthash.h实现
}HashTable;

HashTable* find(HashTable *h, int key){
    HashTable* tmp;
    HASH_FIND_INT(h, &key, tmp);
    return tmp;
}

void insert(HashTable* h, int key, int val){
    HashTable* t = find(h, key);
    if(t == NULL){
        HashTable* tmp = malloc(sizeof(HashTable));
        tmp->key = key;
        tmp->val = val;
        HASH_ADD_INT(h, key, tmp);
    }else{
        t->val = val;
    }
}

int* twoSumHashTable(int* nums, int numSize, int target, int *returnSize){
    HashTable* hashtable = NULL;
    for(int i = 0; i < numSize; i++){
        HashTable* t = find(hashtablem target - nums[i]);
        if (t != NULL){
            int* res = (int*)malloc(sizeof(int) * 2);
            res[0] = t->val, res[1] = i;
            *returnSize = 2;
            return res;
        }
        insert(hashtable, nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

时间复杂度为，空间复杂度为，整体时空效率更为均衡

重识搜索算法

搜索算法用于在数据结构中搜索一个或一组满足特定条件的元素。有两种实现思路

  • 遍历数据结构来定位目标元素

  • 利用数据组织结构或数据包含的先验知识，实现高效元素查找

暴力搜索

通过遍历数据结构的每个元素来定位目标元素

  • 线性搜索：适用于数组和链表等线性数据结构。从一端开始，逐个访问元素，直到找到目标元素或遍历结束

  • 广度优先搜索和深度优先搜索：适用于图和树

优点是简单且通用性好，无须对数据做预处理和借助额外数据结构

自适应搜索

利用数据的特有属性（如有序性）来优化搜索过程，更高效的定位目标元素

  • 二分查找：仅适用于有序数组

  • 哈希查找：将搜索数据和目标数据建立键值对映射

  • 树查找：在特定的树结构中，基于比较节点值来快速排除节点

优点是效率高，时间复杂度可达甚至

缺点是往往需要对数据进行预处理，维护其特有属性需要额外的时间和空间开支

搜索算法的选取

各个搜索算法的工作原理如下

多种搜索策略

操作效率与特性如下

查找算法效率对比

搜索算法的选择还与数据体量、性能要求、查询与更新频率等相关

线性搜索

  • 通用性好，无须预处理。若仅查询一次，其他方法预处理的时间比线性搜索时间还长
  • 适合小体量数据
  • 适合更新频率高数据，无须对数据额外维护

二分查找

  • 适合大体量数据，但由于是数组存储，数据量不能过大
  • 不适合高频增删数据，维护有序数组开销大

哈希查找

  • 适合性能要求很高
  • 不适合有序数据或范围查找，因为哈希表无法维护数据有序性
  • 依赖于哈希函数和哈希冲突处理策略，性能劣化风险较大
  • 不适合数据量过大，哈希表需要额外空间来最大程度减少冲突

树查找

  • 适合海量数据，树节点在内存中分散存储
  • 适合有序数据或范围查找
  • 持续增删时，BST可能倾斜退化为链表；若使用平衡二叉搜索树，效率稳定在，但需额外维护树平衡
  • 标题: 算法：搜索
  • 作者: 敖炜
  • 创建于 : 2023-11-29 18:41:50
  • 更新于 : 2024-04-19 09:30:36
  • 链接: https://ao-wei.github.io/2023/11/29/算法：搜索/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
算法：搜索
  1. 二分查找
    1. 问题描述
    2. 算法思路及实现
    3. 复杂度分析
    4. 优点与局限性
  2. 二分查找插入点
    1. 无重复元素时
    2. 有重复元素时
  3. 二分查找边界
    1. 查找左边界
    2. 查找右边界
  4. 哈希优化策略
    1. 问题描述
    2. 线性查找：以时间换空间
    3. 哈希查找：以空间换时间
  5. 重识搜索算法
    1. 暴力搜索
    2. 自适应搜索
    3. 搜索算法的选取