【033-Search in Rotated Sorted Array（在旋转数组中搜索）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
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.
题目大意
假设一个排序的数组以一个未知的的枢轴旋转。（即，0 1 2 4 5 6 7可能成为4 5 6 7 0 1 2）。 给定一个目标值，在数组中搜寻。如果存在就返回其对应的下标，否则返回-1。 假设数组中不存在重复值。
解题思路
先在数组中找到最小元素对应的下标，如果下标为0说明整个数组是序的，如果不是说明数组被分成两个有序的区间，判断要查找的元素是那一个有序区间中，然后进行查找。
代码实现
算法实现类
{(int[] nums, int target) {if (nums != null && nums.length > 0) {// 找最小元素对应的下标int minIndex = searchMinIndex(nums, 0, nums.length – 1);// 整个数组全局有序if (minIndex == 0) {return binarySearch(nums, 0, nums.length – 1, target);}// 有两个局部有序区间, 如 4 5 6 7 8 9 0 1 2 3 else {// 恬好和后一个有序区间的最后一个元素相等，返回对应的下标if (nums[nums.length – 1] == target) {return nums.length -1;}(nums[nums.length – 1] > target) {return binarySearch(nums, minIndex, nums.length – 1, target);}// target可能是前一个有序区间中else {return binarySearch(nums, 0, minIndex -1, target);}}}return -1;}/*** 二分搜索** @param nums 数组* @param start 起始位置* @param end 结束位置* @param target 搜索目标* @return 匹配元素的下标*/(int[] nums, int start, int end, int target) {int mid;while (start <= end) {mid = start + ((end – start) >> 1);if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {end = mid – 1;} else {start = mid + 1;}}return -1;}/*** 找最小元素的下标** @param nums 数组* @param start 起始位置* @param end 结束位置* @return 最小元素的下标*/(int[] nums, int start, int end) {int mid;while (start < end) {mid = start + ((end – start) >> 1);// 后一个数比前个数小就找到了if (nums[mid] > nums[mid + 1]) {return mid + 1;}(nums[mid] > nums[start]) {start = mid;}// 说明中间值在第二个有序的数组中else {end = mid;}};}}评测结果
点击图片，鼠标不释放，拖动一段位置，，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
人生就是一次充满未知的旅行，在乎的是沿途的风景，
