算法精学--搜索

发表于 分类于

好好的整理一下搜索算法，资料参考于hello算法

一、二分查找

  1. 一般是要求是有序的，无法对无序数组进行查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 在一个有序的数据中查找一个给定的值，使用左闭右闭区间，找到就返回坐标，没找到返回-1
    int binarySearch(vactor<int> &nums, int target){
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            //不要使用(i + j) / 2，可能会超过范围，下面这种写法mid在中间偏左
            int mid = l + (r - l) / 2;  
            if(nums[mid] > target){ //目标在左边
                r = mid - 1;
            }else if(nums[mid] < target){ //目标在右边
                l = mid + 1;
            }else return mid;
        }
        return -1;
    }

  2. 时间复杂度O(logn)，空间复杂度O(1)

  3. 优点和局限性

    • 优点
      • 事件效率高
      • 无需额外的空间
    • 局限性
      • 仅适用于有序数据，如果为了二分查找而排序，得不偿失
      • 只适用于数组，因为需要跳跃查询
      • 在小数据量下，线性查找反而更快，因为只有一次判断，二分查找需要加法，除法，判断等

  4. 二分查找还有很多变形，比如去查找有重复元素的插入位置等，也就是上面的代码判断相等之后，不要直接返回，要继续缩小范围。这是因为 nums 数组中存在重复元素，binary_search_insertion 的目的是找到第一个等于 target 的元素的数组下标

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /* 二分查找插入点（存在重复元素） */
    int binarySearchInsertion(vector<int> &nums, int target) {
        int i = 0, j = nums.size() - 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;
    }

二、搜索算法比较

  1. 搜索算法可以根据实现思路分为

    • 利用遍历的数据结构定位目标，数组、链表、树和图等
    • 利用数据组织结构或数据的包含的先验知识，实现高效的元素查找，二分，哈希和二叉搜索树等

  2. 查找算法效率的比较

    操作 线性搜索 二分查找 树查找 哈希查找
    查找元素 O(n) O(logn) O(logn) O(1)
    插入元素 O(1) O(n) O(logn) O(1)
    删除元素 O(n) O(n) O(logn) O(1)
    额外空间 O(n) O(1) O(n) O(1)
    数据预处理 / 排序O(nlogn) 建树O(nlogn) 建哈希表O(n)
    数据是否有序 无序 有序 有序 无序

  3. 各种算法特点，简单说，线性搜索适用于小型或频率更新的数据；二分查找适用于大型、排序的数据；哈希查找适用于对查询效率要求高且无需范围查询的数据；树查找适用于需要维护顺序和支持范围查询的大型动态数据。

    • 线性搜索
      • 通用性好，无需任何的数据预处理。如果只是需要一次查询，那么其他三种方法的预处理的时间比线性搜索的事件还长
      • 适用于体量较小的数据
      • 适用于数据更新频率较高的场景，不需要对数据进行任何额外的维护
    • 二分查找
      • 使用于大数据量的情况，效率表现稳定，最差也是O(logn)
      • 数据量还不能过大，因为存储数据需要连续的内存空间
      • 不适应于高频的增删数据的场景
    • 哈希查找
      • 适合对查找性能要求较高的场景，平均事件复杂度为O(1)
      • 不适用于有序数据或范围查找的场景，哈希表无法维护数据的有效性
      • 对哈希函数和哈希冲突处理策略的依赖较高，具有较大的性能劣化风险
      • 不适用于数据量过大的情况，因为哈希表需要额外的空间来最大程度的减少冲突，从而提供良好的查询性能
    • 树查询
      • 适用于海量的数据，因为树节点在内存中是分散存储的
      • 适合需要维护有序数据和范围查找的场景
      • 在持续增删节点的过程中，二叉搜索树可能会产生倾斜，事件复杂的劣化至O(n)
      • 若使用AVL树或红黑树，则各项操作在O(logn)效率下稳定运行，但是维护平衡的操作会增加额外开销