首页 > 代码库 > [Leetcode] Find the minimum in rotated sorted array
[Leetcode] Find the minimum 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).
Find the minimum element.
You may assume no duplicate exists in the array.
Tag:
Array; Binary Search
体会：
常规binary search, 但不同于先前去找insert position的那道题。先前那道题要找的target可能是不出现在array中，但是这道题target一定出现在array中，所以循环条件相应改变了，变成当low和high指向同一个index时就停止了。
1. 每次在去找中点值之前，如果当前A[low] - A[high]已经是sorted的部分了，就可以直接返回A[low]了。
2. 在跳动指针的时候注意，如果是A[mid] > A[high]， 指针low可以直接跳过mid，i.e. low = mid + 1, 这是因为既然A[mid]比A[high]大了，那mid上的一定不会是最小值了。相对应的，如果是A[mid] <= A[high]的情况，就不能跳过mid, 因为从这个不等式来看，mid是可能成为最小值的，所以只能有 high = mid.
1 class Solution { 2 public: 3 int findMin(vector<int> &num) { 4 int low = 0; 5 int high = num.size() - 1; 6 // binary search ends when low and high 7 // points to the same index 8 while (low < high) { 9 // already found the sorted part?10 if (num[low] < num[high]) {11 return num[low];12 }13 int mid = low + (high - low) / 2;14 if (num[mid] > num[high]) {15 // since num[mid] > num[high], 16 // num[mid] cannot the minimum, we can17 // jump to mid + 1 safely.18 low = mid + 1;19 } else {20 // num[mid] <= num[high],
//so mid might be the position we want21 // we can not skip mid22 high = mid;23 }24 }25 return num[low];26 }27 };
[Leetcode] Find the minimum in rotated sorted array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。