LeetCode Binary Search 刷题模板
内容提要
本文介绍了LeetCode上的二分查找算法及其应用，包括基本模板、边界处理和题型变换。通过示例题目，如搜索插入位置、搜索二维矩阵和寻找峰值，展示了二分查找在不同问题中的灵活运用，强调了理解算法过程和边界判断的重要性。
延伸解读
二分查找的边界处理：从模板到实战
文章强调二分查找的模板代码是基础，但边界判断才是关键。在搜索插入位置中，返回 low 作为插入点；在寻找峰值中，循环条件改为 low < hi 并调整指针移动方式；在旋转数组中，需判断哪一半有序。这些细节差异说明，死记模板不够，必须理解每一步的边界含义，才能灵活应对变体。
题型变换：如何识别二分查找的适用场景
文章通过多个例题展示了二分查找的变体：搜索二维矩阵将矩阵视为一维数组，寻找峰值利用相邻元素比较，搜索旋转排序数组分析有序部分。这些题目表面不同，但核心都是利用有序性缩小搜索范围。读者应学会将问题转化为在有序序列中查找目标或边界，从而套用二分思想。
旋转数组问题的统一思路
对于搜索旋转排序数组和寻找最小值，文章指出旋转后数组一分为二，必有一半有序。解题时通过比较中间元素与边界元素判断有序部分，进而决定搜索方向。寻找最小值时，比较中间元素与右边界，若中间小于右边界则最小值在左半部分，否则在右半部分。这种思路可推广到其他旋转数组变体。
变通题目：利用插入位置解决频次统计
查找元素的第一个和最后一个位置，以及统计数字出现频次，都可以转化为查找插入位置的问题。通过查找 target 和 target+1 的插入位置，可得到 target 的起始和结束索引，进而计算频次。这种方法避免了复杂的边界判断，直接复用搜索插入位置的代码，体现了二分查找的灵活性和复用性。
Q&A
二分查找算法的基本模板是什么？
二分查找的基本模板包括初始化低指针和高指针，然后在循环中计算中间索引，比较中间元素与目标值的关系，调整指针，直到找到目标或范围为空。
如何在有序数组中查找插入位置？
在有序数组中查找插入位置时，使用二分查找，找到第一个大于等于目标值的索引，如果目标值不存在，则返回其应插入的位置。
如何将二维矩阵转换为一维数组进行二分查找？
将二维矩阵视为一维有序数组，通过计算索引转换为矩阵坐标，在二分查找过程中使用该转换来查找目标值。
寻找峰值元素的二分查找思路是什么？
寻找峰值元素时，修改二分查找算法，通过比较中间元素与相邻元素的大小关系，调整指针以找到峰值。
如何处理旋转排序数组的查找？
在旋转排序数组中查找时，分析数组的有序部分，利用二分查找的原理，判断当前元素与目标值的关系，缩小查找范围。
如何统计数字在数组中出现的频次？
统计数字出现频次的方法是查找目标元素的插入位置和目标元素+1的插入位置，频次等于这两个位置的差值。
