搜索旋转排序数组（二分法实现）

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

注意： 1、你可以假设数组中不存在重复的元素。 2、你的算法时间复杂度必须是 O(log n) 级别。

示例 : 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4

思路

1、算法时间复杂度必须是 O(log n) 级别，第一想到的就是二分法； 2、虽然数组是部分有序的，但通过二分法可以分出一部分是有序的，一部分是无序的，我们只需要判断目标值（target）是否在有序序列中，来决定left和right的选取。 3、核心编程思路：

如果左边有序（[left, mid]），则判断目标值是否在有序序列中，如果在，则right = mid - 1；否则，在右边部分有序的数组中，则left = mid + 1;如果右边有序（[left, mid]），则判断目标值是否在有序序列中，如果在，则left = mid + 1；否则，在左边部分有序的数组中，则right = mid - 1;

实现

public int search(int[] nums, int target) { if(nums == null) return -1; if(nums.length == 1) return nums[0] == target ? 0 : -1; int left = 0; int right = nums.length - 1; while(left <= right){ int mid = (left + right) / 2; if(nums[mid] == target) return mid; if(nums[left] <= nums[mid]){//(left, mid)有序 if(nums[left] <= target && target < nums[mid]){ //目标数值在有序序列中 right = mid - 1; }else{ //目标数值不在有序序列中 left = mid + 1; } }else{//(mid, right)有序 if(nums[mid] < target && target <= nums[right]){ //目标数值在有序序列中 left = mid + 1; }else{ //目标数值不在有序序列中 right = mid - 1; } } } return -1; }