Related: LeetCode 154 - Find Minimum in Rotated Sorted Array II
Find the minimum element in a sorted and rotated array - GeeksforGeeks
http://www.csdn123.com/html/topnews201408/84/5484.htm
http://www.bijishequ.com/detail/134759?p=66
http://www.cnblogs.com/springfor/p/4217615.html
Find the minimum element in a sorted and rotated array - GeeksforGeeks
http://www.csdn123.com/html/topnews201408/84/5484.htm
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).
Find the minimum element.
You may assume no duplicate exists in the array.
X. Recursion
https://www.programcreek.com/2014/02/leetcode-find-minimum-in-rotated-sorted-array/
https://www.programcreek.com/2014/02/leetcode-find-minimum-in-rotated-sorted-array/
public int findMin(int[] num) { return findMin(num, 0, num.length - 1); } public int findMin(int[] num, int left, int right) { if (left == right) return num[left]; if ((right - left) == 1) return Math.min(num[left], num[right]); int middle = left + (right - left) / 2; // not rotated if (num[left] < num[right]) { return num[left]; // go right side } else if (num[middle] > num[left]) { return findMin(num, middle, right); // go left side } else { return findMin(num, left, middle); } }
X.
int findMin(vector<int> &num) {
int low = 0, high = num.size() - 1;
// loop invariant: 1. low < high
// 2. mid != high and thus A[mid] != A[high] (no duplicate exists)
// 3. minimum is between [low, high]
// The proof that the loop will exit: after each iteration either the 'high' decreases
// or the 'low' increases, so the interval [low, high] will always shrink.
while (low < high) {
auto mid = low + (high - low) / 2;
if (num[mid] < num[high])
// the mininum is in the left part
high = mid;
else if (num[mid] > num[high])
// the mininum is in the right part
low = mid + 1;
}
return num[low];
}
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]) {
low = mid + 1;
} else {
high = mid;
}
}
return nums[low];
}
public int findMin(int[] nums) { if(nums==null || nums.length==0) return -1; int i=0; int j=nums.length-1; while(i<=j){ if(nums[i]<=nums[j]) return nums[i]; int m=(i+j)/2; if(nums[m]>=nums[i]){ i=m+1; }else{ j=m; } } return -1; }
https://leetcode.com/articles/find-minimum-in-rotated-sorted-array/
http://www.cnblogs.com/zuoyuan/p/4045742.html
// If the list has just one element then return that element.
if (nums.length == 1) {
return nums[0];
}
// initializing left and right pointers.
int left = 0, right = nums.length - 1;
// if the last element is greater than the first element then there is no
// rotation.
// e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
// Hence the smallest element is first element. A[0]
if (nums[right] > nums[0]) {
return nums[0];
}
// Binary search way
while (right >= left) {
// Find the mid element
int mid = left + (right - left) / 2;
// if the mid element is greater than its next element then mid+1 element is the
// smallest
// This point would be the point of change. From higher to lower value.
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
// if the mid element is lesser than its previous element then mid element is
// the smallest
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}
// if the mid elements value is greater than the 0th element this means
// the least value is still somewhere to the right as we are still dealing with
// elements
// greater than nums[0]
if (nums[mid] > nums[0]) {
left = mid + 1;
} else {
// if nums[0] is greater than the mid value then this means the smallest value
// is somewhere to
// the left
right = mid - 1;
}
}
return -1;
}
http://www.cnblogs.com/zuoyuan/p/4045742.html
下图是这道题的数组的两种情况，分别去处理就可以了
Hint: 二分查找的精髓就在于不断Shrink区间，最后锁定目标值的位置，这也是它的循环不变量。对于这道题来说，关键就在于确定最小值在左还是在右。这并不难，如果发现右半部分是有序的（判断左半部分有序是没用的，最小值既可能是第一个也可能因为旋转在右半部分），则这些值都可以排除掉，只有中点和前半部分的数有可能是最小值，所以就去前半部分继续查找就行了。否则的话则右半部分是乱序，说明最小值在其中。因为每次Shrink区间时不一定会缩小，容易死循环。
https://leetcode.com/discuss/32675/very-simple-java-binary-search
public int searchMinRotatedArray(int[] array, int start ,int end){
if(start == end) return array[start];
int mid = (start+end)/2;
if(array[mid] < array[end])
return searchMinRotatedArray(array, start, mid);
else
return searchMinRotatedArray(array, mid+1, end);
}
https://discuss.leetcode.com/topic/6112/a-concise-solution-with-proof-in-the-comment/
int findMin(vector<int> &num) {
int low = 0, high = num.size() - 1;
// loop invariant: 1. low < high
// 2. mid != high and thus A[mid] != A[high] (no duplicate exists)
// 3. minimum is between [low, high]
// The proof that the loop will exit: after each iteration either the 'high' decreases
// or the 'low' increases, so the interval [low, high] will always shrink.
while (low < high) {
auto mid = low + (high - low) / 2;
if (num[mid] < num[high])
// the mininum is in the left part
high = mid;
else if (num[mid] > num[high])
// the mininum is in the right part
low = mid + 1;
}
return num[low];
}
if the array is indeed rotated by some pivot, there are only 2 possibilities
if the array is not rotated (actually one rotating cycle completed), we just need to go left, in this case a[mid] < a[right] always holds.
combining the cases above, we conclude that
if a[mid] > a[right], go right; if a[mid] < a[right], go left.
public int findMin(int[] nums) {
if (nums==null || nums.length==0) { return Integer.MIN_VALUE; }
int left = 0, right = nums.length-1;
while (left < right-1) { // while (left < right-1) is a useful technique
int mid = left + (right-left)/2;
if (nums[mid] > nums[right]) { left = mid; }
else { right = mid; }
}
if (nums[left] > nums[right]) { return nums[right]; }
return nums[left];
}
http://bangbingsyb.blogspot.com/2014/11/leecode-find-minimum-in-rotated-sorted.html
和Search in Rotated Sorted Array I这题换汤不换药。同样可以根据A[mid]和A[end]来判断右半数组是否sorted：
原数组：0 1 2 4 5 6 7
情况1： 6 7 0 1 2 4 5
情况2： 2 4 5 6 7 0 1
情况1： 6 7 0 1 2 4 5
情况2： 2 4 5 6 7 0 1
(1) A[mid] < A[end]：A[mid : end] sorted => min不在A[mid+1 : end]中
搜索A[start : mid]
(2) A[mid] > A[end]：A[start : mid] sorted且又因为该情况下A[end]<A[start] => min不在A[start : mid]中
搜索A[mid+1 : end]
(3) base case：
a. start = end，必然A[start]为min，为搜寻结束条件。
b. start + 1 = end，此时A[mid] = A[start]，而min = min(A[mid], A[end])。而这个条件可以合并到(1)和(2)中。
int findMin(vector<int> &num) { int start = 0, end = num.size()-1; while(start<end) {//\\ int mid = start+(end-start)/2; if(num[mid]<num[end]) end = mid;//\\ else start = mid+1; } return num[start]; }
http://www.cnblogs.com/springfor/p/4217615.html
首先假设一个sorted没有rotated的数组[1,2,3]，假设我们通过一个pivot把这个数组rotate，那么结果可能为：[2,3,1], [3,1,2], 可以发现：num[low]永远大于（或等于）num[high]。因为你之前是sorted的数组，你在一个sorted的数组找了一个pivot进行rotate，那么比如pivot后面的值都大于pivot之前的值。所以依据这个发现，以及二分法查找。我们可以根据以下判断来解题。num[mid]有两种可能性，如果num[mid] > num[high]，证明num[mid]在rotated后的那个区间内，这个区间我们刚才已知都大于pivot之前的值，所以最小值就在low=mid+1那个区间内。另一种可能，num[mid] <= num[high]，那么我们刚才可以看出来这种可能性说明mid~high以及是排好序的，那么最小值在high=mid这个区间内（mid可能是最小值）。依据此判断可以找到最小值。
1 public int findMin(int[] num) {
2 int low = 0, high = num.length - 1;
3 while (low < high && num[low] >= num[high]) {
4 int mid = (low + high) / 2;
5 if (num[mid] > num[high])
6 low = mid + 1;
7 else
8 high = mid;
9 }
10 return num[low];
11 }
http://blog.csdn.net/linhuanmars/article/details/205256812 int low = 0, high = num.length - 1;
3 while (low < high && num[low] >= num[high]) {
4 int mid = (low + high) / 2;
5 if (num[mid] > num[high])
6 low = mid + 1;
7 else
8 high = mid;
9 }
10 return num[low];
11 }
- public int findMin(int[] num) {
- if(num == null || num.length==0)
- return 0;
- int l = 0;
- int r = num.length-1;
- int min = num[0];
- while(l<r-1)
- {
- int m = (l+r)/2;
- if(num[l]<num[m])
- {
- min = Math.min(num[l],min);
- l = m+1;
- }
- else if(num[l]>num[m])
- {
- min = Math.min(num[m],min);
- r = m-1;
- }
- else
- {
- l++;
- }
- }
- min = Math.min(num[r],min);
- min = Math.min(num[l],min);
- return min;
- }
public int FindMin(int[] nums) {
int left = 0, right = nums.Length - 1, mid = 0;
while(left < right){
mid = (left + right) >> 1;
if(nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[right];
}
I think both nums[right] and nums[left] should be OK in this case, because when breaking the while loop, "left" should be equal to "right".
public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return -1; } int start = 0, end = nums.length - 1; int target = nums[nums.length - 1]; // find the first element <= target while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] <= target) { end = mid; } else { start = mid; } } if (nums[start] <= target) { return nums[start]; } else { return nums[end]; } }
X. https://discuss.leetcode.com/topic/5170/java-solution-with-binary-search
X. Different way - not better
http://www.programcreek.com/2014/02/leetcode-find-minimum-in-rotated-sorted-array/
http://buttercola.blogspot.com/2015/08/leetcode-find-minimum-in-rotated-sorted.html
The minimum element must satisfy one of two conditions: 1) If rotate, A[min] < A[min - 1]; 2) If not, A[0]. Therefore, we can use binary search: check the middle element, if it is less than previous one, then it is minimum. If not, there are 2 conditions as well: If it is greater than both left and right element, then minimum element should be on its right, otherwise on its left.
public int findMin(int[] num) {
if (num == null || num.length == 0) {
return 0;
}
if (num.length == 1) {
return num[0];
}
int start = 0, end = num.length - 1;
while (start < end) {
int mid = (start + end) / 2;
if (mid > 0 && num[mid] < num[mid - 1]) {
return num[mid];
}
if (num[start] <= num[mid] && num[mid] > num[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return num[start];
}http://www.programcreek.com/2014/02/leetcode-find-minimum-in-rotated-sorted-array/
http://buttercola.blogspot.com/2015/08/leetcode-find-minimum-in-rotated-sorted.html
3 Compares in the loop.
public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int lo = 0; int hi = nums.length - 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (nums[lo] < nums[hi]) {// return nums[lo]; } else if (nums[mid] < nums[hi]) { hi = mid; } else if (nums[lo] < nums[mid]) { lo = mid; } } return Math.min(nums[lo], nums[hi]); }
How to handle duplicates?
It turned out that duplicates can’t be handled in O(Logn) time in all cases. Thanks to Amit Jain for inputs. The special cases that cause problems are like {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} and {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}. It doesn’t look possible to go to left half or right half by doing constant number of comparisons at the middle. Following is an implementation that handles duplicates. It may become O(n) in worst case though.
http://www.csdn123.com/html/topnews201408/84/5484.htm
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.
if (num == null)
return -1;
int len = num.length;
int lo = 0, hi = len - 1;
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (num[mid] < num[lo])
lo = mid;
else
hi = mid - 1;
}
return num[lo] <= num[hi]? num[lo]: num[hi];
}
https://leetcode.com/discuss/55773/java-solution-naive-and-optimized-method
O(N)
public int findMin(int[] nums) { int min = nums[0]; for(int i = 1; i < nums.length; i++){ if(min > nums[i]) min = nums[i]; } return min; }
http://bookshadow.com/weblog/2014/10/16/leetcode-find-minimum-rotated-sorted-array/
-- not good
def findMin(self, num): ans = num[0] size = len(num) low, high = 0, size - 1 while low <= high: mid = (low + high) / 2 if num[mid] <= num[high]: #min位于左侧上升沿 high = mid - 1 else: #min位于左侧上升沿与右侧上升沿之间 low = mid + 1 ans = min(ans, num[mid]) return ans
Read full article from Find the minimum element in a sorted and rotated array - GeeksforGeeks
It turned out that duplicates can’t be handled in O(Logn) time in all cases. Thanks to Amit Jain for inputs. The special cases that cause problems are like {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} and {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}. It doesn’t look possible to go to left half or right half by doing constant number of comparisons at the middle. Following is an implementation that handles duplicates. It may become O(n) in worst case though.
http://www.csdn123.com/html/topnews201408/84/5484.htm
public int findMin(int[] num) { 3 if (num == null || num.length == 0) { 4 return 0; 5 } 6 7 int len = num.length; 8 if (len == 1) { 9 return num[0]; 10 } else if (len == 2) { 11 return Math.min(num[0], num[1]); 12 } 13 14 int left = 0; 15 int right = len - 1; 16 17 while (left < right - 1) { 18 int mid = left + (right - left) / 2; 19 // In this case, the array is sorted. 20 // 这一句很重要，因为我们移除一些元素后，可能会使整个数组变得有序... 21 if (num[left] < num[right]) { 22 return num[left]; 23 } 24 25 // left side is sorted. CUT the left side. 26 if (num[mid] > num[left]) { 27 left = mid; 28 // left side is unsorted, right side is sorted. CUT the right side. 29 } else if (num[mid] < num[left]) { 30 right = mid; 31 } else { 32 left++; 33 } 34 } 35 36 return Math.min(num[left], num[right]); 37 }http://blog.csdn.net/linhuanmars/article/details/40449299
- public int findMin(int[] num) {
- if(num == null || num.length==0)
- return 0;
- int l = 0;
- int r = num.length-1;
- int min = num[0];
- while(l<r-1)
- {
- int m = (l+r)/2;
- if(num[l]<num[m])
- {
- min = Math.min(num[l],min);
- l = m+1;
- }
- else if(num[l]>num[m])
- {
- min = Math.min(num[m],min);
- r = m-1;
- }
- else
- {
- l++;
- }
- }
- min = Math.min(num[r],min);
- min = Math.min(num[l],min);
- return min;
- }
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.
int findRotations(const vector<int> &arr, int low, int high){if( arr[low] <= arr[high] )return low;int len = arr.size();int mid = (low + high) / 2;int prev = (mid - 1 + len) % len; //if mid is at 0, consider last element as previousint next = (mid + 1) % len; // if mid is the last element, consider next element as the firstif( arr[mid] < arr[prev] && arr[mid] < arr[next] )return mid;if( arr[low] <= arr[mid] ) // if left half is sorted, search in the right halfreturn findRotations(arr, mid+1, high);elsereturn findRotations(arr, low, mid-1); // search in the right half}http://hehejun.blogspot.com/2015/01/algorithmfind-minimum-in-rotated-sorted.html
在原题Find Minimum in Rotated Sorted Array中，array的顺序是从小到大的。这次我们把array的顺序改成从大到小，解法会发生什么变化吗？通过这一题，我们会总结二分法边界条件的相关问题。public int findMin(int[] num) {这一题的分析思路是和原题是一样的，同样为了代码的简洁我们比较A[lo]和A[mid]：
- 如果A[mid] < A[lo]，那么[lo, mid]是sorted的，minimum只可能在[mid, hi]区间里。
- 如果A[mid] < A[lo]，那么[mid, hi]不是sorted的，minimum只可能在[lo, mid)区间里。
所以如果A[mid] < A[lo]，我们更新lo = mid；如果A[mid] < A[lo] 我们更新hi = mid - 1。但是随之而来的问题就是和原题不同，当我们把lo复制为mid的时候，当hi == lo + 1的时候，二分就无法向下进行了，因为mid会一直等于lo。所以这个时候当hi <= lo + 1的时候我们就应该跳出，然后找lo和hi中较小的那一个。分析到这里，我们可以看出，当二分的策略不同的时候，边界条件也是不同的，具体总结如下：
- [lo, hi] -> [lo, mid) + (mid, hi]，这个时候每次更新的时候lo = mid + 1，hi = mid - 1，跳出的条件至少应该是lo > hi
- [lo, hi] -> [lo, mid] + (mid, hi]，这个时候每次更新的时候lo = mid + 1，hi = mid，跳出的条件至少应该是lo >= hi，若条件为lo >= hi，跳出的时候情况为lo == hi
- [lo, hi] -> [lo, mid) + [mid, hi]，这个时候每次更新的时候lo = mid，hi = mid - 1，跳出的条件至少应该是lo + 1 >= hi，若条件为lo + 1 >= hi，跳出的时候情况为lo == hi 或者 lo + 1 == hi
- [lo, hi] -> [lo, mid) + (mid, hi]，这个时候每次更新的时候lo = mid，hi = mid，跳出的条件至少应该是lo + 1 >= hi，若条件为lo + 1 >= hi，跳出的时候情况为 lo + 1 == hi
if (num == null)
return -1;
int len = num.length;
int lo = 0, hi = len - 1;
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (num[mid] < num[lo])
lo = mid;
else
hi = mid - 1;
}
return num[lo] <= num[hi]? num[lo]: num[hi];
}
https://leetcode.com/discuss/55773/java-solution-naive-and-optimized-method
O(N)
public int findMin(int[] nums) { int min = nums[0]; for(int i = 1; i < nums.length; i++){ if(min > nums[i]) min = nums[i]; } return min; }
http://bookshadow.com/weblog/2014/10/16/leetcode-find-minimum-rotated-sorted-array/
-- not good
def findMin(self, num): ans = num[0] size = len(num) low, high = 0, size - 1 while low <= high: mid = (low + high) / 2 if num[mid] <= num[high]: #min位于左侧上升沿 high = mid - 1 else: #min位于左侧上升沿与右侧上升沿之间 low = mid + 1 ans = min(ans, num[mid]) return ans
Read full article from Find the minimum element in a sorted and rotated array - GeeksforGeeks
