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. 7
  2. 6
  3. ─────┼───────────
  4. 5
  5. 4
  6. 3
  7. 2
  8. 1
  1. 7
  2. 6
  3. 5
  4. 4
  5. 3
  6. ───────────┼───────────
  7. 2
  8. 1

本题依旧可以用二分查找,难度主要在于左右边界的确定。仔细观察上面两幅图,我们可以得出如下结论:

如果A[left] <= A[mid],那么[left,mid] 一定为单调递增序列。

代码

  1. // Search in Rotated Sorted Array
  2. // Time Complexity: O(log n),Space Complexity: O(1)
  3. public class Solution {
  4. public int search(int[] nums, int target) {
  5. int first = 0, last = nums.length;
  6. while (first != last) {
  7. final int mid = first + (last - first) / 2;
  8. if (nums[mid] == target)
  9. return mid;
  10. if (nums[first] <= nums[mid]) {
  11. if (nums[first] <= target && target < nums[mid])
  12. last = mid;
  13. else
  14. first = mid + 1;
  15. } else {
  16. if (nums[mid] < target && target <= nums[last-1])
  17. first = mid + 1;
  18. else
  19. last = mid;
  20. }
  21. }
  22. return -1;
  23. }
  24. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/search/search-in-rotated-sorted-array.html