Hello 算法10：搜索

https://www.hello-algo.com/chapter_searching/binary_search/

二分查找法

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

# 首先初始化 i=0,j=n-1, 代表搜索区间是[0,n-1]
# 然后，循环执行以下2个步骤
# 1：m = (i+j)/2 ,向下取整，求出搜索区间的中间点
# 2：判断nums[m]和target的大小关系，有以下三种情况：
#    a：nums[m] > target,说明目标在区间[i,m-1],所以让j = m - 1
#    b: nums[m] < target,说明目标在区间[m+1,j],所以让i = m + 1
#    c：说明已经找到目标值，因此返回索引m

代码如下：

def binary_search(nums: list[int], target: int):
    i, j = 0, len(nums) - 1
    while i <= j:
        m = (i+j) // 2
        if nums[m] > target:
            j = m -1
        elif nums[m] < target:
            i = m + 1
        else:
            return m
    return -1

优点：效率高，无需额外空间

缺点：仅适用于有序数据，仅使用数数组搜索，当数据量较小时，线性查找速度更快。

二分查找插入点

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

1. 当target存在时，插入的索引就是taget的位置
2. 当target不存在时：如果target > nums[m]，让i = m +1 ，所以i在靠着大于等于目标的位置移动；反之j在靠着小于等于目标的位置移动，这导致的结果就是，最终i等于第一个比目标大的元素，j指向首个比目标小的元素。

可知，最终返回i即是插入的位置

def binary_search_insertion_simple(nums: list[int], target: int) -> int:
    """二分查找插入点（无重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # target 在区间 [i, m-1] 中
        else:
            return m  # 找到 target ，返回插入点 m
    # 未找到 target ，返回插入点 i
    return i

重复值的情况

在上一题的基础上，规定数组可能包含重复元素，其余不变

def binary_search_insertion(nums: list[int], target: int) -> int:
    """二分查找插入点（存在重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1  # target 在区间 [i, m-1] 中
        else:
            j = m - 1  # 首个小于 target 的元素在区间 [i, m-1] 中
    # 返回插入点 i
    return i

查找左边界

def binary_search_left_edge(nums: list[int], target: int) -> int:
    """二分查找最左一个 target"""
    # 等价于查找 target 的插入点
    i = binary_search_insertion(nums, target)
    # 未找到 target ，返回 -1
    if i == len(nums) or nums[i] != target:
        return -1
    # 找到 target ，返回索引 i
    return i

查找右边界

替换在 nums[m] == target 情况下的指针收缩操作即可，接下来介绍一些取巧的办法

1. 复用左边界法，使查找目标加一

   def binary_search_right_edge(nums: list[int], target: int) -> int:
       """二分查找最右一个 target"""
       # 转化为查找最左一个 target + 1
       i = binary_search_insertion(nums, target + 1)
       # j 指向最右一个 target ，i 指向首个大于 target 的元素
       j = i - 1
       # 未找到 target ，返回 -1
       if j == -1 or nums[j] != target:
           return -1
       # 找到 target ，返回索引 j
       return j
   

2. 转换为查找不存在的元素

   当数组不包含目标元素时，最终i和j会分别指向首个大于、小于target的元素：

   查找最左侧元素时，可以将目标设置为targe-0.5，最终返回i

   查找最右侧元素时，可以将目标设置为target+0.5，最终返回j

   

哈希优化

在算法题中，通常通过将线性遍历替换为哈希搜索来提升时间复杂度。例如以下题目

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

线性遍历

开启一个两层循环，每次判断是否和为目标值。简单粗暴

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    """方法一：暴力枚举"""
    # 两层循环，时间复杂度为 O(n^2)
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[i] == target:
                return [i, j]
    return []

哈希查找

def two_sum_hash_table(nums: list[int], target: int) -> list[int]:
    """方法二：辅助哈希表"""
    # 辅助哈希表，空间复杂度为 O(n)
    dic = {}
    n = len(nums)
    for i in range(n):
        if target - nums[i] not in dic:
            dic[nums[i]] = i
        else:
            return [dic[target - nums[i]], i]
    return []

搜索算法总结

搜索算法根据实现方式可以分为以下两类：

• 通过遍历数据结构来定位元素，例如数组、图、树的遍历等
• 利用数据结构的特性，实现高效搜索，例如二分查找、哈希查找

暴力搜索

• 线性搜索，适用于数组、链表
• 广度优先和深度优先搜索，适用于图、树

优点是通用性好，容易理解，不需要对数据结构做预期处理；不需要额外空间。

缺点是此类算法的时间复杂度为O(n)，因此在元素较多时效率较低

自适应搜索

自适应搜索利用数据结构的特性来优化搜索

• 二分查找，利用有序性来进行搜索，仅适用于数组
• 哈希查找，利用哈希表将搜索数据和目标数据建立键值对映射，从而实现查询操作
• 树查找

效率高，可达到o(logn)甚至o(1)

缺点：需要对数据进行预处理，需要额外空间

搜索方法选取

表 10-1 查找算法效率对比

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