代码功能分析
这段代码实现了在旋转排序数组中搜索目标值的功能。旋转排序数组是指一个原本有序的数组在某个点进行了旋转，例如[4,5,6,7,0,1,2]是由[0,1,2,4,5,6,7]旋转得到的。
算法思路
算法采用二分查找的变种，通过比较中间元素与左右边界的关系，确定目标值可能位于哪一侧。具体逻辑分为两种情况：
- 如果左半部分是有序的（
nums[0] <= nums[mid]），检查目标值是否在该有序范围内。 - 如果右半部分是有序的（
nums[0] > nums[mid]），检查目标值是否在该有序范围内。
关键步骤
- 初始化左右指针
l和r，分别指向数组的起始和末尾。 - 计算中间位置
mid，检查是否等于目标值。 - 根据中间值与左边界的关系，判断哪一部分是有序的。
- 在有序部分中检查目标值是否存在，调整指针位置。
时间复杂度
算法的时间复杂度为 $O(\log n)$，因为每次迭代都将搜索范围减半。
空间复杂度
空间复杂度为 $O(1)$，仅使用了常数级别的额外空间。
代码优化点
- 中间值计算可以改为
mid = l + (r - l) / 2，避免潜在的整数溢出问题。 - 可以提前处理一些边界情况，例如数组长度为 0 或 1 时直接返回结果。
示例测试
cpp复制插入
vector<int> nums = {4,5,6,7,0,1,2}; int target = 0; Solution sol; int result = sol.search(nums, target); // 应返回 4复制插入
边界条件
- 空数组：直接返回 -1。
- 单元素数组：检查是否等于目标值。
- 目标值不存在于数组中：返回 -1。
- 目标值为数组的第一个或最后一个元素：确保能够正确识别。
