💡
原文中文，约6000字，阅读约需15分钟。
📝
内容提要
本文介绍了LeetCode上的二分查找算法及其应用，包括基本模板、边界处理和题型变换。通过示例题目，如搜索插入位置、搜索二维矩阵和寻找峰值，展示了二分查找在不同问题中的灵活运用，强调了理解算法过程和边界判断的重要性。
🎯
关键要点
- 二分查找算法属于双指针类型，需要学习边界处理和题型变换的技巧。
- 搜索插入位置题目要求在有序数组中找到目标值的索引或插入位置，时间复杂度为O(log n)。
- 搜索二维矩阵题目可以将矩阵视为一维有序数组，需注意索引转换为矩阵坐标。
- 寻找峰值题目通过修改二分查找算法，判断中间元素与相邻元素的关系来找到峰值。
- 搜索旋转排序数组题目需要分析旋转后的数组，确定有序部分进行二分查找。
- 寻找旋转排序数组中的最小值题目同样利用二分查找，判断中间元素与右边界元素的关系。
- 变通题目如查找元素的第一个和最后一个位置，可以通过查找插入位置的方式解决。
- 统计数字在数组中出现频次的题目与查找元素位置类似，需查找目标元素和目标元素+1的插入位置。
❓
延伸问答
二分查找算法的基本模板是什么？
二分查找的基本模板包括初始化低指针和高指针，然后在循环中计算中间索引，比较中间元素与目标值的关系，调整指针，直到找到目标或范围为空。
如何在有序数组中查找插入位置？
在有序数组中查找插入位置时，使用二分查找，找到第一个大于等于目标值的索引，如果目标值不存在，则返回其应插入的位置。
如何将二维矩阵转换为一维数组进行二分查找？
将二维矩阵视为一维有序数组，通过计算索引转换为矩阵坐标，在二分查找过程中使用该转换来查找目标值。
寻找峰值元素的二分查找思路是什么？
寻找峰值元素时，修改二分查找算法，通过比较中间元素与相邻元素的大小关系，调整指针以找到峰值。
如何处理旋转排序数组的查找？
在旋转排序数组中查找时，分析数组的有序部分，利用二分查找的原理，判断当前元素与目标值的关系，缩小查找范围。
如何统计数字在数组中出现的频次？
统计数字出现频次的方法是查找目标元素的插入位置和目标元素+1的插入位置，频次等于这两个位置的差值。
➡️
