题目描述整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., 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)的算法解决此问题。示例 1输入nums [4,5,6,7,0,1,2], target 0输出4示例 2输入nums [4,5,6,7,0,1,2], target 3输出-1示例 3输入nums [1], target 0输出-1解题思路方法二分查找核心思路旋转后的数组从中间切开至少有一半是有序的[4, 5, 6, 7, 0, 1, 2] ↑ mid3 左半部分 [4, 5, 6, 7] 有序 右半部分 [0, 1, 2] 有序判断哪一半有序然后看 target 是否在有序的那一半中。算法步骤计算mid如果nums[mid] target返回mid判断左半部分是否有序nums[left] nums[mid]如果左半部分有序如果nums[left] target nums[mid]在左半部分找 →right mid - 1否则在右半部分找 →left mid 1如果右半部分有序如果nums[mid] target nums[right]在右半部分找 →left mid 1否则在左半部分找 →right mid - 1具体过程示例nums [4, 5, 6, 7, 0, 1, 2],target 0初始: left0, right6, mid3 [4, 5, 6, 7, 0, 1, 2] ↑ ↑ ↑ left mid right nums[mid]7 ! 0 nums[left]4 nums[mid]7 → 左半部分有序 target0 不在 [4, 7) 中 → 在右半部分找 left mid1 4 left4, right6, mid5 [4, 5, 6, 7, 0, 1, 2] ↑ ↑ ↑ left mid right nums[mid]1 ! 0 nums[left]0 nums[mid]1 → 左半部分有序 target0 在 [0, 1) 中 → 在左半部分找 right mid-1 4 left4, right4, mid4 nums[mid]0 target → 返回 4 ✅代码实现class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } // 判断左半部分是否有序 if (nums[left] nums[mid]) { // 左半部分有序 if (nums[left] target target nums[mid]) { right mid - 1; // target 在左半部分 } else { left mid 1; // target 在右半部分 } } else { // 右半部分有序 if (nums[mid] target target nums[right]) { left mid 1; // target 在右半部分 } else { right mid - 1; // target 在左半部分 } } } return -1; } };复杂度分析维度复杂度说明时间复杂度O(log n)每次排除一半空间复杂度O(1)只用常数个变量关键细节1. 为什么用nums[left] nums[mid]判断左半部分有序如果nums[left] nums[mid]说明左半部分没有旋转点是有序的否则旋转点在左半部分右半部分有序2. 为什么用而不是因为nums[mid]可能等于nums[left]比如left mid时用更安全。3. 边界条件if (nums[left] target target nums[mid])target nums[mid]不是因为nums[mid] target已经在前面判断过了nums[left] target是因为nums[left]可能就是 target4. 和「搜索旋转排序数组 II」的区别题目区别33. 搜索旋转排序数组值互不相同81. 搜索旋转排序数组 II值可能重复81 题需要额外处理nums[left] nums[mid] nums[right]的情况。总结要点说明核心思想二分查找判断哪一半有序关键判断nums[left] nums[mid]判断左半部分有序时间复杂度O(log n)空间复杂度O(1)