首页 > 代码库 > leetcode 154/153. Find Minimum in Rotated Sorted Array && II

leetcode 154/153. Find Minimum in Rotated Sorted Array && II

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).

Find the minimum element.

You may assume no duplicate exists in the array.

分析:

对不包含重复元素的数组A[0, ... , n - 1], 如果A[mid] < A[high], 说明最小值在A[low, mid]之间。

否则,在A[mid + 1, high]之间。

 1 int findMin(vector<int> &num)  2     { 3         int low = 0, high = num.size() - 1, mid = 0; 4          5         while (low < high) 6         { 7             mid = (low + high) / 2; 8             if (num[mid] < num[high]) 9                 high = mid;10             else 11                 low = mid + 1;12         }13         14         return num[low];15     }

 如果A包含重复元素,需要加入判断A[mid] == A[high], 此时不能使用二分,如 [1, 1, 0, 1]和[0, 1, 1, 1], 最小元素

可以在A[mid, high], 也可能在A[low, mid], 此时可以high--, 减少区间范围。

 1 int findMin(vector<int> &num)  2     { 3         int low = 0, high = num.size() - 1, mid = 0; 4         while (low < high) 5         { 6             mid = (low + high) / 2; 7             if (num[mid] == num[high]) 8                 high--; 9             else if (num[mid] < num[high])10                 high = mid;11             else12                 low = mid + 1;13         }14         15         return num[low];16     }

 

leetcode 154/153. Find Minimum in Rotated Sorted Array && II