查找算法--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# 没找到就返回-1return -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# 没找到返回-1return -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) - 1while 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) - 1while 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) - 1while 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)。这就是典型的空间换时间，