一、题目
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
二、解题思路
- 初始化两个指针，
left和right，分别指向数组的开始和结束。 - 当
left小于right时，执行以下步骤： a. 计算中间位置mid。 b. 如果nums[mid]等于target，则返回mid。 c. 判断nums[left]和nums[mid]之间的值是否有序：- 如果有序，说明
target必须在left和mid之间，更新right为mid - 1。 - 如果无序，说明
target必须在mid和right之间，更新left为mid + 1。
- 如果有序，说明
- 如果循环结束还没有找到
target，则返回-1。
三、具体代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 如果找到了目标值
if (nums[mid] == target) {
return mid;
}
// 判断左右两边哪一边是有序的
if (nums[left] <= nums[mid]) {
// 左边有序，target 在左边
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// 右边有序，target 在右边
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
// 循环结束，如果 left 等于 right 且 nums[left] 等于 target，则返回 left
// 否则返回 -1
return nums[left] == target ? left : -1;
}
}四、时间复杂度和空间复杂度
1. 时间复杂度
- 时间复杂度是 O(log n)。
- 这是因为在每次迭代中，搜索范围都会减半。
- 这是二分查找算法的典型特征，其中
n是数组的长度。 - 在最坏的情况下，需要进行 log(n) 次迭代才能找到目标值或确定目标值不存在。
2. 空间复杂度
- 空间复杂度是 O(1)。
- 这个算法是原地进行的，不需要额外的存储空间。
- 所有的计算都是在常量级别的额外空间内完成的，例如使用几个辅助变量（
left,right,mid）。 - 这些变量的数量不随着输入数据的规模变化，因此空间复杂度是常数级别的。
五、总结知识点
1. 二分查找算法（Binary Search）：
- 这是一种在有序数组中查找特定元素的高效算法。
- 通过不断将搜索范围减半，二分查找可以在对数时间内找到目标值或确定目标值不存在。
2. 旋转排序数组的处理：
- 由于数组是旋转过的，它不再是完全有序的，这就需要在二分查找的基础上进行调整。
- 通过比较数组的两端（
left和right）以及中间点（mid）的值，可以确定哪一半是有序的，并据此调整搜索范围。
3. 条件判断和循环控制：
- 使用
while循环来重复执行二分查找的过程，直到找到目标值或搜索范围为空。 - 使用
if和else语句来判断数组的哪一半是有序的，并据此更新搜索范围的边界。
4. 数组索引的更新：
- 根据中间点
mid的值与目标值target的关系，以及数组的有序性，更新left和right的值。
5. 返回值的处理：
- 如果在循环结束后
left和right相遇，并且nums[left]等于target，则返回left。 - 如果
left和right相遇，但nums[left]不等于target，则返回-1表示目标值不存在于数组中。
6. 防止整数溢出：
- 在计算
mid时，使用left + (right - left) / 2而不是(left + right) / 2来避免可能的整数溢出问题。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
