Related: LeetCode - Search in Rotated Sorted Array II
Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.
This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.
Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations?
For example the array [4, 5, 1, 2, 3] is (right) rotated twice.
http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
http://www.jiuzhang.com/solutions/search-in-rotated-sorted-array/
http://www.ideserve.co.in/learn/find-an-element-in-a-sorted-rotated-array-without-finding-pivot
A complementary question to this problem could be to identify the rotation pivot position itself.
Observer that the rotation pivot is the left most element of the sorted part of the array. The sorted part of the array id characterized by the fact that leftmost element is less than the rightmost element (i.e. elements are in strictly increasing order). We can do a binary search on the rotated array until we satisfy this condition. While doing binary search, If we are in the rotated part of the array then the middle element is always higher than the rightmost element. So, we should search in the right part of the middle element. If the middle is in sorted part then we continue searching on the left as the right part of middle is in order now.
X. If we know the index of min
https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14425/Concise-O(log-N)-Binary-search-solution
Method 2 (Efficient Using Binary Search)
Here are also we find index of minimum element, but using Binary Search. The idea is based on below facts :
If we take closer look at examples, we can notice that the number of rotations is equal to index of minimum element. A simple linear solution is to find minimum element and returns its index. Below is C++ implementation of the idea.
Read full article from Searching an Element in a Rotated Sorted Array | LeetCode
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.
X.
https://cheonhyangzhang.wordpress.com/2016/11/09/33-leetcode-java-search-in-rotated-sorted-array-hard/
https://discuss.leetcode.com/topic/16580/java-ac-solution-using-once-binary-search
http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
http://blog.csdn.net/linhuanmars/article/details/20525681
这道题是二分查找Search Insert Position的变体，看似有点麻烦，其实理清一下还是比较简单的。因为rotate的缘故，当我们切取一半的时候可能会出现误区，所以我们要做进一步的判断。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14436/Revised-Binary-Search
https://discuss.leetcode.com/topic/16580/java-ac-solution-using-once-binary-search
https://discuss.leetcode.com/topic/34467/pretty-short-c-java-ruby-python
https://cheonhyangzhang.wordpress.com/2016/11/09/33-leetcode-java-search-in-rotated-sorted-array-hard/
If the sorted array is not rotated, then this is a question of standard binary search. However, when the array is rotated, we will need some modification of standard binary search.
Modify the checking condition when moving start and end pivot in standard binary search. We get the mid element of given start and end. If the element equals the target, then good, we can return the index.
After we calculate the mid index, let’s see where the mid is at. In the picture above, there are two cases for the mid point. Either at A or at B.
When mid is at A, we need to find a way to determine if we want to go to the left half or right half. We can see that the easier way is to check the left half, which is nums[start] <=target < nums[mid]. Otherwise, it's falling into the right half.
Similar strategy applies for the case when mid is at point B.
When mid is at A, we need to find a way to determine if we want to go to the left half or right half. We can see that the easier way is to check the left half, which is nums[start] <=target < nums[mid]. Otherwise, it's falling into the right half.
Similar strategy applies for the case when mid is at point B.
public int search(int[] nums, int target) { int start = 0, end = nums.length - 1; while (start <= end) { int mid = ( start + end) / 2; if (nums[mid] == target) { return mid; } if (nums[start] <= nums[mid]) { if (nums[start] <= target && target < nums[mid]) { end = mid -1; } else { start = mid + 1; } } else{ if (nums[mid] < target && target <= nums[end]) { start = mid + 1; } else { end = mid -1; } } } return -1; }http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
The idea is that when rotating the array, there must be one half of the array that is still in sorted order.
For example, 6 7 1 2 3 4 5, the order is disrupted from the point between 7 and 1. So when doing binary search, we can make a judgement that which part is ordered and whether the target is in that range, if yes, continue the search in that half, if not continue in the other half.
For example, 6 7 1 2 3 4 5, the order is disrupted from the point between 7 and 1. So when doing binary search, we can make a judgement that which part is ordered and whether the target is in that range, if yes, continue the search in that half, if not continue in the other half.
public int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end){
int mid = (start + end) / 2;
if (nums[mid] == target)
return mid;
if (nums[start] <= nums[mid]){//\\ we can just use < as there is no duplicate
if (target < nums[mid] && target >= nums[start])
end = mid - 1;
else
start = mid + 1;
}
if (nums[mid] <= nums[end]){//\\
if (target > nums[mid] && target <= nums[end])
start = mid + 1;
else
end = mid - 1;
}
}
return -1;
}这道题是二分查找Search Insert Position的变体，看似有点麻烦，其实理清一下还是比较简单的。因为rotate的缘故，当我们切取一半的时候可能会出现误区，所以我们要做进一步的判断。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。代码如下
- public int search(int[] A, int target) {
- if(A==null || A.length==0)
- return -1;
- int l = 0;
- int r = A.length-1;
- while(l<=r)
- {
- int m = (l+r)/2;
- if(target == A[m])
- return m;
- if(A[m]<A[r])
- {
- if(target>A[m] && target<=A[r])
- l = m+1;
- else
- r = m-1;
- }
- else
- {
- if(target>=A[l] && target<A[m])
- r = m-1;
- else
- l = m+1;
- }
- }
- return -1;
- }
https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14436/Revised-Binary-Search
https://discuss.leetcode.com/topic/16580/java-ac-solution-using-once-binary-search
public int search(int[] A, int target) {
int lo = 0;
int hi = A.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (A[mid] == target) return mid;
if (A[lo] <= A[mid]) {
if (target >= A[lo] && target < A[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if (target > A[mid] && target <= A[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return A[lo] == target ? lo : -1;
}https://discuss.leetcode.com/topic/34467/pretty-short-c-java-ruby-python
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}
题目一看就知道是binary search。所以关键点在于每次要能判断出target位于左半还是右半序列。解这题得先在纸上写几个rotated sorted array的例子出来找下规律。Rotated sorted array根据旋转得多少有两种情况：
原数组：0 1 2 4 5 6 7
情况1： 6 7 0 1 2 4 5 起始元素0在中间元素的左边
情况2： 2 4 5 6 7 0 1 起始元素0在中间元素的右边
两种情况都有半边是完全sorted的。根据这半边，当target != A[mid]时，可以分情况判断：
当A[mid] < A[end] < A[start]：情况1，右半序列A[mid+1 : end] sorted
A[mid] < target <= A[end], 右半序列，否则为左半序列。
当A[mid] > A[start] > A[end]：情况2，左半序列A[start : mid-1] sorted
A[start] <= target < A[mid], 左半序列，否则为右半序列
Base case：当start + 1 = end时
假设 2 4:
A[mid] = A[start] = 2 < A[end]，A[mid] < target <= A[end] 右半序列，否则左半序列
假设 4 2:
A[mid] = A[start ] = 4 > A[end], A[start] <= target < A[mid] 左半序列，否则右半序列
加入base case的情况，最终总结的规律是：
A[mid] = target, 返回mid，否则
(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end] 右半，否则左半。
(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid] 左半，否则右半。
原数组：0 1 2 4 5 6 7
情况1： 6 7 0 1 2 4 5 起始元素0在中间元素的左边
情况2： 2 4 5 6 7 0 1 起始元素0在中间元素的右边
两种情况都有半边是完全sorted的。根据这半边，当target != A[mid]时，可以分情况判断：
当A[mid] < A[end] < A[start]：情况1，右半序列A[mid+1 : end] sorted
A[mid] < target <= A[end], 右半序列，否则为左半序列。
当A[mid] > A[start] > A[end]：情况2，左半序列A[start : mid-1] sorted
A[start] <= target < A[mid], 左半序列，否则为右半序列
Base case：当start + 1 = end时
假设 2 4:
A[mid] = A[start] = 2 < A[end]，A[mid] < target <= A[end] 右半序列，否则左半序列
假设 4 2:
A[mid] = A[start ] = 4 > A[end], A[start] <= target < A[mid] 左半序列，否则右半序列
加入base case的情况，最终总结的规律是：
A[mid] = target, 返回mid，否则
(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end] 右半，否则左半。
(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid] 左半，否则右半。
int searchRotatedSortedArray(int A[], int start, int end, int target) { if(start>end) return -1; int mid = start + (end-start)/2; if(A[mid]==target) return mid; if(A[mid]<A[end]) { // right half sorted if(target>A[mid] && target<=A[end]) return searchRotatedSortedArray(A, mid+1, end, target); else return searchRotatedSortedArray(A, start, mid-1, target); } else { // left half sorted if(target>=A[start] && target<A[mid]) return searchRotatedSortedArray(A, start, mid-1, target); else return searchRotatedSortedArray(A, mid+1, end, target); } }
int search(int A[], int n, int target) { int start = 0, end = n-1; while(start<=end) { int mid = start + (end-start)/2; if(A[mid]==target) return mid; if(A[mid]<A[end]) { // right half sorted if(target>A[mid] && target<=A[end]) start = mid+1; else end = mid-1; } else { // left half sorted if(target>=A[start] && target<A[mid]) end = mid-1; else start = mid+1; } } return -1; }
int rotated_binary_search(int A[], int N, int key) {
int L = 0;
int R = N - 1;
while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == key) return M;
// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}
Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.
This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.
int FindSortedArrayRotation(int A[], int N) {
int L = 0;
int R = N - 1;
while (A[L] > A[R]) {
int M = L + (R - L) / 2;
if (A[M] > A[R])
L = M + 1;
else
R = M;
}
return L;
}
http://comproguide.blogspot.com/2014/03/how-many-times-sorted-array-is-rotated.htmlGiven a circularly sorted array of unique elements, how do we efficiently find the number of rotations?
For example the array [4, 5, 1, 2, 3] is (right) rotated twice.
http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
public int search(int[] nums, int target) { int left = 0; int right= nums.length-1; while(left<=right){ int mid = left + (right-left)/2; if(target==nums[mid]) return mid; if(nums[left]<=nums[mid]){ if(nums[left]<=target&& target<nums[mid]){ right=mid-1; }else{ left=mid+1; } }else{ if(nums[mid]<target&& target<=nums[right]){ left=mid+1; }else{ right=mid-1; } } } return -1; } |
public int search(int[] A, int target) { if (A == null || A.length == 0) { return -1; } int start = 0; int end = A.length - 1; int mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (A[mid] == target) { return mid; } if (A[start] < A[mid]) { // situation 1, red line if (A[start] <= target && target <= A[mid]) { end = mid; } else { start = mid; } } else { // situation 2, green line if (A[mid] <= target && target <= A[end]) { start = mid; } else { end = mid; } } } // while if (A[start] == target) { return start; } if (A[end] == target) { return end; } return -1; }http://www.zrzahid.com/search-in-a-sorted-but-rotated-array/
public static int searchInSortedRotatedArray(int a[], int key){ int l = 0; int h = a.length-1; int mid; while(l < h){ mid = (l+h)/2; if(a[mid] == key){ return mid; } //search in left subtree else if(a[mid] > key){ //if left subtree has rotated part if(a[l] > key){ l = mid+1; } //otherwise its in sorted part else{ h = mid-1; } } else{ //if right subtree has rotated part if(a[h] < key){ h = mid-1; } //otherwise its in sorted part else{ l = mid+1; } } } return -1; }
http://www.ideserve.co.in/learn/find-an-element-in-a-sorted-rotated-array-without-finding-pivot
public static int findElementUsingBinarySearch(int[] array, int num) { if(array == null || array.length == 0) { return -1; } int start = 0; int end = array.length-1; while(start <= end) { int mid = (start + end)/2; if(num == array[mid]) { return mid; } if(array[start] <= array[mid]) { // array[start...mid] is sorted if(array[start] <= num && num <= array[mid]) { // num lies between array[start...mid] end = mid-1; } else { start = mid+1; } } else { // array[mid...end] is sorted if(array[mid] <= num && num <= array[end]) { // num lies between array[mid...end] start = mid+1; } else { end = mid-1; } } } return -1; }Observer that the rotation pivot is the left most element of the sorted part of the array. The sorted part of the array id characterized by the fact that leftmost element is less than the rightmost element (i.e. elements are in strictly increasing order). We can do a binary search on the rotated array until we satisfy this condition. While doing binary search, If we are in the rotated part of the array then the middle element is always higher than the rightmost element. So, we should search in the right part of the middle element. If the middle is in sorted part then we continue searching on the left as the right part of middle is in order now.
public static int findRotationPositin(final int[] a) { if (a.length <= 1) { return 0; } int l = 0; int r = a.length - 1; int m = (l + r) / 2; while (a[l] > a[r]) { m = (l + r) / 2; if (a[m] > a[r]) { l = m + 1; } else { r = m; } } return l; }
X. Recursive
http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
public int search(int[] nums, int target) { return binarySearch(nums, 0, nums.length-1, target); } public int binarySearch(int[] nums, int left, int right, int target){ if(left>right) return -1; int mid = left + (right-left)/2; if(target == nums[mid]) return mid; if(nums[left] <= nums[mid]){ if(nums[left]<=target && target<nums[mid]){ return binarySearch(nums,left, mid-1, target); }else{ return binarySearch(nums, mid+1, right, target); } }else { if(nums[mid]<target&& target<=nums[right]){ return binarySearch(nums,mid+1, right, target); }else{ return binarySearch(nums, left, mid-1, target); } } } |
X. If we know the index of min
https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14425/Concise-O(log-N)-Binary-search-solution
int search(int A[], int n, int target) {
int lo=0,hi=n-1;
// find the index of the smallest value using binary search.
// Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
// Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
while(lo<hi){
int mid=(lo+hi)/2;
if(A[mid]>A[hi]) lo=mid+1;
else hi=mid;
}
// lo==hi is the index of the smallest value and also the number of places rotated.
int rot=lo;
lo=0;hi=n-1;
// The usual binary search and accounting for rotation.
while(lo<=hi){
int mid=(lo+hi)/2;
int realmid=(mid+rot)%n;
if(A[realmid]==target)return realmid;
if(A[realmid]<target)lo=mid+1;
else hi=mid-1;
}
return -1;
}
Consider an array of distinct numbers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.
Here are also we find index of minimum element, but using Binary Search. The idea is based on below facts :
- The minimum element is the only element whose previous is greater than it. If there is no previous element element, then there is no rotation (first element is minimum). We check this condition for middle element by comparing it with (mid-1)’th and (mid+1)’th elements.
- If minimum element is not at middle (neither mid nor mid + 1), then minimum element lies in either left half or right half.
- If middle element is smaller than last element, then the minimum element lies in left half
- Else minimum element lies in right half.
// Returns count of rotations for an array which// is first sorted in ascending order, then rotatedint countRotations(int arr[], int low, int high){ // This condition is needed to handle the case // when array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = low + (high - low)/2; /*(low + high)/2;*/ // Check if element (mid+1) is minimum element. // Consider the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid+1] < arr[mid]) return (mid+1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left half or // right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid-1); return countRotations(arr, mid+1, high);}int countRotations(int arr[], int n){ // We basically find index of minimum // element int min = arr[0], min_index; for (int i=0; i<n; i++) { if (min > arr[i]) { min = arr[i]; min_index = i; } } return min_index;}