本文主要是介绍LeetCode Search in Rotated Sorted Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
题意：
给定一个已经排好序的数组，然后按照某个元素旋转，给定一个目标数字，求在这个旋转数组中出现这个目标数字的位置(下标)，如果没有出现，那么返回-1，否则返回出现的下标。
题解：
采用和之前的搜索旋转数组的最小元素的方法，先找到那个最小的元素，用二分搜索找，找到这个元素也就意味着找到了分界点，这个最小元素左边的必定大于这个元素，而且已经排好序了，这个最小元素右边的必定也大于这个元素，而且也已经排好序了。但是为了防止出现超时现象，有几种特殊情况需要当心，首先是当这个数组的长度只为1，那么我们只要查看这个头元素是否等于target，如果相等，那么直接返回0，否则就返回-1，也就不用去执行了；如果找到这个最小元素的位置，也就是分界点，那么查看这个分界点的值是不是等于target，如果相等，直接返回这个分界点的位置(下标)，否则如果这个分界点是0，那么只要做一遍二分搜索即可，否则对分界点两边都要做一遍二分搜索。
public int search(int[] nums,int target){int length = nums.length;if(length == 1 && nums[0] == target)return 0;else if(length == 1 && nums[0] != target)return -1;int min = searchBinary(nums,0,length - 1);if(nums[min] == target)return min;if(min == 0)return binary(nums,0,length - 1,target);System.out.println(min);if(binary(nums,0,min -1,target) != -1)return binary(nums,0,min -1,target);else if(binary(nums,0,min -1,target) == -1){if(binary(nums,min,length - 1,target) != -1)return binary(nums,min,length - 1,target);else return -1;}return -1;}public int searchBinary(int[] nums,int start,int end){int length = nums.length;if(nums[start] < nums[end])return start;while(nums[start] >= nums[end]){if(start + 1 == end)return end;int mid = (start + end) / 2;if(nums[mid] >= nums[start])start = mid;else if(nums[mid] <= nums[end])end = mid;}return end;}public int binary(int[] nums,int start,int end,int target){if(start <= end){int mid = (start + end) / 2;if(nums[mid] == target)return mid;if(nums[mid] < target)return binary(nums,mid + 1,end,target);else if(nums[mid] > target)return binary(nums,start,mid - 1,target);}return -1;}这篇关于LeetCode Search in Rotated Sorted Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
