【无标题】搜索旋转排序数组

代码功能分析

这段代码实现了在旋转排序数组中搜索目标值的功能。旋转排序数组是指一个原本有序的数组在某个点进行了旋转，例如[4,5,6,7,0,1,2]是由[0,1,2,4,5,6,7]旋转得到的。

算法思路

算法采用二分查找的变种，通过比较中间元素与左右边界的关系，确定目标值可能位于哪一侧。具体逻辑分为两种情况：

1. 如果左半部分是有序的（nums[0] <= nums[mid]），检查目标值是否在该有序范围内。
2. 如果右半部分是有序的（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。
• 目标值为数组的第一个或最后一个元素：确保能够正确识别。