首页 > 其他 > 详细

Leetcode#153 Find Minimum in Rotated Sorted Array

时间:2015-01-30 10:37:44      阅读:245      评论:0      收藏:0      [点我收藏+]

原题地址

 

简化版本的Find Minimum in Rotated Sorted Array II(参见这篇文章

二分查找最小值,每次只需要查看其中一个二分区间即可。

如果A[i] < A[j]则说明A[i..j]肯定是连续的,说明这一段的最小值是A[i],之后就可以把这一段砍掉去看另一半即可。

如果A[i] > A[j]则说明A[i..j]肯定是非连续的,说明最小值肯定出现在A[i..j]中当中,之后继续在这一半内查找,另一半可以砍掉了。

 

代码:

 1 int findMin(vector<int> &num) {
 2         int l = 0;
 3         int r = num.size() - 1;
 4         int res = num[0];
 5         
 6         while (l <= r) {
 7             int m = (l + r) / 2;
 8             if (num[l] <= num[m]) {
 9                 res = min(res, num[l]);
10                 l = m + 1;
11             }
12             else {
13                 res = min(res, num[m]);
14                 r = m - 1;
15             }
16         }
17         
18         return res;
19 }

 

Leetcode#153 Find Minimum in Rotated Sorted Array

原文:http://www.cnblogs.com/boring09/p/4261639.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!