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 public int search(int[] A, int target) { 2         int first = 0, last = A.length; 3         while (first != last) { 4             int mid = (first + last) / 2; 5             if (A[mid] == target) 6                 return mid; 7             if (A[first] <= A[mid]) { 8                 if (A[first] <= target && target < A[mid]) 9                     last = mid;10                 else11                     first = mid + 1;12             } else {13                 if (A[mid] < target && target <= A[last - 1])14                     first = mid + 1;15                 else16                     last = mid;17             }18         }19         return -1;20     }

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

允许重复，造成了如果A[m]>=A[l], 那么[l,m] 为递增序列的假设就不能成立了，比如[1,3,1,1,1]。

如果A[m]>=A[l] 不能确定递增，那就把它拆分成两个条件：

• 若A[m]>A[l]，则区间[l,m] 一定递增

• 若A[m]==A[l] 确定不了，那就l++，往下看一步即可。

因此复杂度从O(lgn)变成了O(n)。具体说明参见剑指offer上查找旋转数组的最小元素。

1 public boolean search(int[] A, int target) { 2         int first = 0, last = A.length; 3         while (first != last) { 4             int mid = (first + last) / 2; 5             if (A[mid] == target) 6                 return true; 7             if (A[first] < A[mid]) { 8                 if (A[first] <= target && target < A[mid]) 9                     last = mid;10                 else11                     first = mid + 1;12             } else if (A[first] > A[mid]) {13                 if (A[mid] < target && target <= A[last - 1])14                     first = mid + 1;15                 else16                     last = mid;17             } else {18                 first++;19             }20         }21         return false;22     }