一、二分查找算法介绍
二分查找(Binary Search)也称为折半查找，如果一个查找问题能够用一个条件消除一半的查找区域，那么就对目标在特定空间搜索，从而减少查找空间。
它是一种在有序数组中查找某一特定元素的搜索算法，每一次比较都使搜索范围缩小一半。二分查找的时间复杂度是O(logn)。
算法基础流程：
1) 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。
2) 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
3) 如果在某一步骤数组为空，则代表找不到。
二、二分查找算法实例 - 俄罗斯套娃信封问题
2.1 需求描述
1) 输入：一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
2) 要求：当下一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
3) 求解：最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
2.2 需求分析设计
1) 套信封，有两个维度：宽和高
2) 我们先将“宽”升序排序，同样高的信封，按照“高”降序排序(同样宽或者高的信封，无法套在一起，降序可以天然避免同高，不等宽的信封做额外是否可以“套”的处理)
3) 基于第2步的“有序序列”，将“最多能有多少个信封”转化为了求“最长子序列问题”
4) 使用二分查找方法，求取套信封子序列的最大长度
2.3 代码(附详细注释，不在单独解释代码逻辑)
#-*- coding:utf-8 -*-
#二分查找算法实例 - 俄罗斯套娃信封问题
# 1) 套信封，有两个维度：宽和高
# 2) 我们先将“高”升序排序，同样高的信封，按照“宽”降序排序(同样宽或者高的信封，无法套在一起，降序可以天然避免同高，不等宽的信封做额外是否可以“套”的处理)
# 3) 基于第2步的“有序序列”，将“最多能有多少个信封”转化为了求“最长子序列问题”
# 4) 使用二分查找方法，查找套信封子序列的最大长度
def binary_search_evelopes(ev_list:list[int]):
? ? #先将信封按照宽升序、高降序，排序，将“最多能有多少个信封”转化为了求“最长子序列问题”
? ? #envelopes[i] = [wi, hi]
? ? ev_list = sorted(ev_list, key=lambda x:(x[0], -x[1]))
? ?
? ? # print('sorted list:', ev_list)
? ?
? ? #使用二分查找方法，求取套信封子序列的最大长度
? ? max_ASC_list = []
? ? for val in ev_list:
? ? ? ? #定义最长子序列，二分查找的前后滑动指针
? ? ? ? left_index = 0
? ? ? ? right_index = len(max_ASC_list)
? ? ? ? #在max_ASC_list中通过二分查找，求取最长子序列长度
? ? ? ? while(left_index < right_index):
? ? ? ? ? ? #获取中间值的索引，折半查找开始
? ? ? ? ? ? mid_index = left_index + ((right_index - left_index)//2)
? ? ? ? ? ? #取当前值，用于max_ASC_list中折半查找
? ? ? ? ? ? #由于宽是有序的，所以只需比较高即可
? ? ? ? ? ? current_value = val[1]
? ? ? ? ? ?
? ? ? ? ? ? #如果等于中位值，则已命中，终止循环
? ? ? ? ? ? if(max_ASC_list[mid_index] == current_value ):
? ? ? ? ? ? ? ? left_index = mid_index
? ? ? ? ? ? ? ? break ?
? ? ? ? ? ? #如果当前信封的高大于中位值，则将在右侧区域继续比较，则滑动左侧索引
? ? ? ? ? ? elif(max_ASC_list[mid_index] < current_value):
? ? ? ? ? ? ? ? left_index = mid_index + 1
? ? ? ? ? ? #反之则在左侧区域继续比较
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? right_index = mid_index - 1
? ? ? ?
? ? ? ? # print('ev_list[i][0] =', val[1])
? ? ? ? #如果当前元素值大于子序列中最大的值，则加入最大子序列 ? ? ?
? ? ? ? if left_index == len(max_ASC_list):
? ? ? ? ? ? max_ASC_list.append(val[1])
? ? ? ? #如果比当前子序列中的值小，则替换子序列的值；
? ? ? ? #1、替换并不会导致子序列长度增长，因为他不比最外层的信封更大，无法再套一层
? ? ? ? #2、替换为更小的值，是由于后续的值比更小的值来说，更可能加入最大子序列（套信封更容易）
? ? ? ? else:
? ? ? ? ? ? max_ASC_list[left_index] = val[1]
? ? ? ? ? ?
? ? return len(max_ASC_list)
if __name__ == '__main__':
? ? #示例 1
? ? #输入
? ? ev_list = [[5,4],[6,4],[6,7],[2,3]]
? ? #输出：3, 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]
? ? print(binary_search_evelopes(ev_list))
? ?
? ? #示例 2
? ? #输入
? ? ev_list = envelopes = [[1,1],[1,1],[1,1]]
? ? #输出：1
? ? print(binary_search_evelopes(ev_list))
? ?
? ?
? ? #示例 3
? ? #输入
? ? ev_list = [[5,4],[6,4],[6,7],[2,1],[3,3],[6,4],[6,8],[7,9]]
? ? #输出：5, 最多信封的个数为 5, 组合为: [2,1] => [3,3]=> [5,4] => [6,7] => [7,9]
? ? print(binary_search_evelopes(ev_list))2.4 结果验证
PS D:\Shangouxuehui_Git\PythonAlgorithm-main> & D:/Python312/python.exe d:/Shangouxuehui_Git/PythonAlgorithm-main/sgxh_binary_search.py
3
1
5源码下载：
https://github.com/ShanGouXueHui/PythonAlgorithm
##山狗学会 License Start##
转载请注明出处，"今日头条"创作者"山狗学会“ ，注明出处即授权，未注明出处罚款100万元
主页链接：山狗学会主页
##山狗学会 License End##