1. 题目描述

题目中转：33. 搜索旋转排序数组

2.详细题解

    给定数组是严格有序的，但在某个位置的下标处进行了旋转，因此改变了数组有序的特性，但数组局部是有序的，虽可以使用算法复杂度为$O(n)$的算法进行逐一遍历查找目标值的索引，但未能利用局部有序的特性。属于在有序的数组中查找数据，首先想到二分查找算法，但该题能使用二分查找算法吗？答案是肯定的，因为数组是局部有序的，如何利用数组局部有序特性呢？在中间数据将数组划分为两个区间时，先判断是左区间有序还是右区间有序，再判断目标值是否在有序的区间内？根据结果再更新相应的左或右指针。 从而利用数组局部有序的特性。
  具体算法如下：

• Step1：初始化：两个指针 left 和 right，分别指向数组的起始和结束位置；
• Step2：计算中间元素的索引： mid = (left + right) / 2；
• Step3：如果 nums[mid] == target，则找到目标值，返回 mid，程序结束；
• Step4：否则判断那个区间有序：
•   如果nums[mid] >= nums[left]的值，说明左区间有序；
•   否则右区间有序；
• Step4：如果左区间有序:
•   如果目标值在左区间内，则更新$right=mid-1$；
•   否则在右区间内，则更新$left=mid+1$;
• Step5：如果右区间有序（同理）:
•   如果目标值在右区间内，则更新$left=mid+1$；
•   否则在右区间内，则更新$right=mid-1$;
• Step6：当指针left小于right时，重复步骤Step2_Step6；
• Step6：否则返回-1。

  注意，在具体代码实现时，一定要注意边界条件，尤其容易忽略。

3.代码实现

3.1 Python

python">class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = (left +right) // 2if nums[mid] == target:return midif nums[left] <= nums[mid]:  # 若左边区间有序if nums[left] <= target < nums[mid]:right = mid - 1else:left = mid + 1else:  # 否则，右边区间有序if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1

3.2 Java

java">class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right){int mid = (left + right) / 2;if (nums[mid] == target){return mid;}else if (nums[mid] > nums[left]){// 左区间有序if (nums[left] <= target && target < nums[mid]){right = mid - 1;}else{left = mid + 1;}}else{// 右区间有序if (nums[mid] < target && target <= nums[right]){left = mid + 1;}else{right = mid - 1;}}}return -1;}
}

  将错误测试例子$[3,1]$代入程序分析，发现$mid$首次的值为$3$，根据程序判断为左区间无序（$if(nums[mid]>nums[left])$），则右区间有序，故首先判断目标值是否在右区间范围内，右区间为$[3,1]$（但实际是无序的），根据程序判断目标值不在右区间内（$if(nums[mid]<target\&\&target<=nums[right])$），故右指针更新为$right=mid-1=-1$，循环条件不满足而推出循环，最终返回-1。但实际该测试案例是有正确值的，在程序初次判断左区间是否有序时存在问题，单独的区间$[3]$是有序而非无序的，而右区间$[3,1]$是无序而非有序，因此应该修改此次代码边界条件，首先判断目标值是否在有序的左区间，不在则更新$左指针left=mid+1=1$，再进行下一轮判断即可返回正确的目标值所在索引为$1$。优化代码如下：

java">class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right){int mid = (left + right) / 2;if (nums[mid] == target){return mid;}else if (nums[mid] >= nums[left]){// 左区间有序if (nums[left] <= target && target < nums[mid]){right = mid - 1;}else{left = mid + 1;}}else{// 右区间有序if (nums[mid] < target && target <= nums[right]){left = mid + 1;}else{right = mid - 1;}}}return -1;}
}

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code。