题目：
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 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。
方法一：
首先通过二分查找找出数组中最小值的位置。这样我们可以将数组分成2段，使得每一段都是有序的。之后看要查找的数(target)的值落在哪一段，然后再在这一段里进行一次二分查找即可。
方法二：（推荐）
对于每一轮二分查找，中点的左侧和右侧必然有有一边是有序的。我们看看target是不是在有序的这个范围内，是的话就查这一边，不是的话就查另一边。
代码：
方法一：Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class Solution { public int search(int[] nums, int target) { // First binary search for finding the index of minimum value. int lo = 0; int hi = nums.length - 1; while(lo < hi){ int mi = lo + (hi - lo) / 2; if(nums[mi] > nums[hi]) lo = mi + 1; else hi = mi; } int min = nums[lo]; // Second binary search for finding target. if(target >= min && target <= nums[nums.length - 1]){ hi = nums.length - 1; } else { hi = lo - 1; lo = 0; } while(lo <= hi){ int mi = lo + (hi - lo) / 2; if(nums[mi] == target) return mi; else if(nums[mi] < target) lo = mi + 1; else hi = mi - 1; } return -1; } } |
方法二：Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class Solution { public int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mi = lo + (hi - lo)/2; if (nums[mi] == target) return mi; if (nums[lo] < nums[mi]) { //left half is sorted if (nums[lo] <= target && lo < mi && target <= nums[mi - 1]) hi = mi - 1; else lo = mi + 1; } else { //right half is sorted if (mi < hi && nums[mi + 1] <= target && target <= nums[hi]) lo = mi + 1; else hi = mi - 1; } } return -1; } } |