- Suppose an array sorted in ascending order 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.
- time: o(logn) space: o(1)
- public int search(int[] nums, int target) {
- if (nums == null || nums.length == 0) return - 1;
- int left = 0,
- right = nums.length - 1;
- while (left + 1 < right) {
- int mid = left + (right - left) / 2;
- if (nums[mid] == target) return mid;
- //break into two parts: note, there is no duplicate
- //first half
- if (nums[left] < nums[mid]) {
- if (target <= nums[mid] && nums[left] <= target) {
- right = mid;
- } else {
- left = mid;
- }
- }
- //second half: 注意判断顺序变化: 考虑单调的, 避开非单调的!
- else {
- if (nums[mid] <= target && target <= nums[right]) {
- left = mid;
- } else {
- right = mid;
- }
- }
- }
- //post processing for the left and right
- if (nums[left] == target) {
- return left;
- }
- if (nums[right] == target) {
- return right;
- }
- return - 1;
- }
来源: http://www.bubuko.com/infodetail-2506231.html