LeetCode#33和#34的二分查找算法解析

#33 旋转排序数组中的查找

题目描述了一个原本按升序排列的整数数组，在未知的某个点进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。任务是在这个数组中查找指定的目标值 target，如果找到了，则返回其索引；如果没有找到，则返回 -1。

#34 查找目标值的起始和结束位置

本题给出一个已按升序排列且可能含有重复元素的整数数组 nums 和一个目标值 target。目标是找到 target 在数组中的起始和结束位置。如果 target 不在数组中，则返回 [-1, -1]。

二分查找的应用

二分查找是一种高效的查找算法，适用于有序数组，其时间复杂度为 O(log n)。基本原理是在每次迭代中，通过比较中间元素与目标值来决定搜索范围是左半部分还是右半部分，从而逐步缩小搜索范围，直至找到目标值或确定目标值不存在。

解题策略

对于题目 #33，由于数组经过了旋转，导致整个数组不是完全有序的，但可以将其视为由两个有序子数组组成。在应用二分查找时，每次分割都会产生一个有序子数组和一个可能无序的子数组。通过检查中间值及其两侧的值，可以确定哪一部分是有序的，并据此判断目标值是否位于有序子数组内。如果是，则在该子数组内继续搜索；如果不是，则在另一部分继续搜索，直到找到目标值或确认不存在。

对于题目 #34，尽管数组是完全有序的，但由于可能存在重复元素，直接应用标准的二分查找可能无法直接得到起始和结束位置。解决方法是进行两次二分查找：第一次查找目标值的起始位置，第二次查找结束位置。每次查找时，当找到目标值时，不立即停止，而是调整边界以确保覆盖所有相同值的元素，最终确定目标值的完整范围。