查找算法--python

二分查找

一、概述

基于有序数组的一种查找算法，主要使用了分治的思想，在每次查找的过程后，都能缩小一半的搜索范围，比如在1到100内猜数字，在保险的情况下先说50，根据结果再分析范围是1到49、51到100还是就是50，可以大大的减少查询次数。

二、查找元素位置

步骤

• 设置边界，一般left取0作为左边界，right取lenth - 1作为右边界
• 计算mid = (left + right) // 2，查看中间值，并和target比较
• 当nums[mid] < target时，说明目标值在中间值的右边，此时更新左边界为mid + 1
• 当nums[mid] > target时，说明目标值在中间值的左边，此时更新右边界为mid - 1
• 当nums[mid] = target时，说明找到目标值，返回mid值，也就是目标值的位置索引

例如–左闭右闭

def binary_search(nums: list[int], target: int):
    # 确定搜索边界
    left, right = 0, len(nums) - 1
    # 在右边界大于等于左边界时一直搜
    while left <= right:
        # 寻找中间值,这种写法是为了防止越界(在python中很少)
        mid = left + (right - left) // 2
        # 当中间值小于目标值时，左边界挪到中间值右边一位
        if nums[mid] < target:
            left = mid + 1
        # 当中间值大于目标值时，右边界挪到中间值左边一位
        elif nums[mid] > target:
            right = mid - 1
        # 找到目标值，直接返回位置
    	else:
            return mid
    # 没找到就返回-1
    return -1

这种为区间左闭右闭的情况，一般来说，因为python中有很多“包左不包右”的情况，所以左闭右开的区间也很常见，当这种情况发生时，判断条件中的left=right就不可能发生了，会导致找不到目标值或者返回错误的目标，所以我们做一下修改。

例如–左闭右开

def binary_search(nums: list[int], target: int):
    # 设置边界为左闭右开
    left, right = 0, len(nums)
    # 左右边界不会相等，去除相等的条件
    while left < right:
        # 寻找中间值,这种写法是为了防止越界(在python中很少)
        mid = left + (right - left) // 2
        # 当中间值小于目标值时，左边界挪到中间值右边一位
        if nums[mid] < target:
            left = mid + 1
        # 当中间值小于目标值时，因为左边界取不到，左边界挪到中间值位置
    	elif nums[mid] > target:
            right = mid
        # 找到后返回索引
    	else:
            return mid
    # 没找到返回-1
    return -1

左开右闭也是同理，后续的区间范围要和开始的相同(闭或者开)。

三、查找元素插入位置

上述章节中，我们发现在元素不存在时，我们直接返回了-1，那么如果元素不存在后，我们现在想插入这个元素，该怎么用二分查找查到元素的插入位置呢。

此时我们也要分两种情况，有重复元素和没有重复元素的情况，其中无重复元素情况相较简单我们先分析。

1、无重复元素

首先最重要的是，在选择插入时，我们要找的索引是什么，此时有两个情况：

• 元素中本身就包括target时：就插入到当前target的位置。
• 元素中不包括target时：经过简单分析可以得出，插入的位置为首个比当前元素大的元素的位置(可能有点拗口)，我们的目的就是去找到这个位置，后续插入该位置。

def binary_search_insert(nums: list[int], target: int):
    # 确认查找的左右边界
    left, right = 0, len(nums) - 1
    # 在右边界大于等于左边界时一直搜
    while left <= right:
        # 寻找中间值,这种写法是为了防止越界(在python中很少)
        mid = left + (right - left) // 2
        # 当中间值小于目标值时，左边界挪到中间值右边一位
        if nums[mid] < target:
            left = mid + 1
        # 当中间值大于目标值时，右边界挪到中间值左边一位
        elif nums[mid] > target:
            right = mid - 1
       	# 找到了目标值
        else:
            return mid
    # 没找到，此时左边的边界就是我们要找的插入点
    return left

2、有重复元素

上述是无重复元素的情况，位置比较好找，就是首个大于当前元素的位置，但是当有重复元素的时候，没有办法去确认该元素有多少个，如果是直接插入的话，则找到就行，不过此时我们想要去插入到区间的最左边，此时我们需要找到首个小于target的位置。

def binary_search_insert(nums: list[int], target: int):
    # 确认查找的左右边界
    left, right = 0, len(nums) - 1
    while left <= right:
        # 寻找中间值,这种写法是为了防止越界(在python中很少)
        mid = left + (right - left) // 2
        # 当中间值小于目标值时，左边界挪到中间值右边一位
        if nums[mid] < target:
            left = mid + 1
        # 当中间值大于目标值时，右边界挪到中间值左边一位
        elif nums[mid] > target:
            right = mid - 1
       	# 缩小右边界直到找到首个小于目标值的元素
        else:
            right = mid - 1
    # 此时左边的边界就是我们要找的最左边
    return left

四、查找元素边界

与上文类似，当我们插入一个值的时候，可能会出现该列表中已经有多个类似的值了，此时我们想要知道重复元素的区间范围，可以复用上述插入的思想。

查找右边界

def binary_search_right(nums: list[int], target: int):
    # 确认查找的左右边界
    left, right = 0, len(nums) - 1
    while left <= right:
        # 寻找中间值,这种写法是为了防止越界(在python中很少)
        mid = left + (right - left) // 2
        # 当中间值小于目标值时，左边界挪到中间值右边一位
        if nums[mid] < target + 1:
            left = mid + 1
        # 当中间值大于目标值时，右边界挪到中间值左边一位
        elif nums[mid] > target + 1:
            right = mid - 1
       	# 缩小右边界直到找到首个小于目标值的元素
        else:
            right = mid - 1
    # 此时左边的边界就是我们要找的首个大于目标值的插入点
    index = left
    # 此时的左边界-1就是我们要找的目标值的右边界
    res = left - 1
    # 右边界不合法说明没有元素
    if res == -1 or nums[res] != target:
        return -1
   	# 返回右边界
    return res

查找左边界

def binary_search_left(nums: list[int], target: int):
    # 确认查找的左右边界
    left, right = 0, len(nums) - 1
    while left <= right:
        # 寻找中间值,这种写法是为了防止越界(在python中很少)
        mid = left + (right - left) // 2
        # 当中间值小于目标值时，左边界挪到中间值右边一位
        if nums[mid] < target:
            left = mid + 1
        # 当中间值大于目标值时，右边界挪到中间值左边一位
        elif nums[mid] > target:
            right = mid - 1
       	# 缩小右边界直到找到首个小于目标值的元素
        else:
            right = mid - 1
    # 此时左边的边界就是我们要找的目标值左边界
    index = left
    # 左边界不合法说明没有元素
    if index == len(nums) or nums[index] != target:
        return -1
   	# 返回左边界
    return index

五、小结

二分查找的效率很高，时间复杂度为O(logn)，而且该算法不需要额外的内存来做排序。

不过二分查找最大的弊端就是需要时有序的序列，而排序算法的复杂度通常都在O(nlogn)以上，反而比线性查找更慢；而且二分查找只能作用于数组，不适合用于链表当中。

哈希查找

该查找可以用力扣第一题来理解：https://leetcode.cn/problems/two-sum/description/

这题的常规思路肯定是直接两层遍历，枚举出符合条件的数字，但是时间复杂度为O(n²)，当数据量很大时，时间会非常长，此时我们就可以用哈希查找去做优化。

众所周知，哈希是键值对相互对应的，此时我们建立一个哈希表，将值和索引存到 哈希表中，后续查找的时候就可以直接利用键值对的关系找到第二个值了。

def twoSum(nums: List[int], target: int) -> List[int]:
    # 列表长度
    lenth = len(nums)
    # 建立字典
    nums_dict = {}
    # 遍历列表
    for i in range(lenth):
        # 获得另一个值的是多少
        tmp = target - nums[i]
        # 如果另一个值在字典中，直接返回索引
        if tmp in nums_dict:
            return [nums_dict[tmp], i]
       	# 如果没有就加新键值对
        nums_dict[nums[i]] = i
    # 没有合适的两个值
    return []

时间复杂度降到O(n)，相对的空间复杂度从O(1)上升到O(n)。这就是典型的空间换时间，