http://changhaz.wordpress.com/2014/10/15/leetcode-find-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.

Solution:
Classic binary search problem. One place worth noticing is the termination conditions. Whenever our window has only one element, its value is the answer. When our window has two elements, and the first element is larger than the second one, the second element is our answer. This case falls into the num[mid]>=num[start] condition in the code below. (given that there is no duplicates in the array)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMin(vector<int> &num) {
        int start=0,end=num.size()-1;
 
        while (start<end) {
            if (num[start]<num[end])
                return num[start];
 
            int mid = (start+end)/2;
 
            if (num[mid]>=num[start]) {
                start = mid+1;
            } else {
                end = mid;
            }
        }
 
        return num[start];
    }
};
 

最新文章

  1. 【bzoj2648】 SJY摆棋子
  2. session在本地可以正常使用，而在sae上却无法使用或者值为空的解决方法
  3. Python3 windows如何安装模块 setuptools
  4. C#中进行单元测试
  5. UVa 136 Ugly Numbers【优先队列】
  6. Javascript里，想把一个整数转换成字符串，字符串长度为2
  7. C#实现在Winform中嵌入Word和Excel
  8. Oracle常用查看表结构命令
  9. jquery利用event.which方法获取键盘输入值的代码
  10. Parallelogram Counting（平行四边形个数，思维转化）
  11. RF环境安装-mac-osx10.10-基础环境-安装指南
  12. 多线程随笔二（Task）
  13. 免费开源的boostrap模板
  14. ABP+AdminLTE+Bootstrap Table权限管理系统第一节--使用ASP.NET Boilerplate模板创建解决方案
  15. Python基础篇(六)
  16. 优雅使用 illuminate/database 包中的 Collection
  17. IOS开发中将定时器添加到runLoop中
  18. MongoDB 基本操作和聚合操作
  19. (90)Wangdao.com第二十三天_JavaScript CSS 操作
  20. 冲刺博客NO.10

热门文章

  1. prim和kruskal算法
  2. mysql并发更新问题
  3. 使用c#特性，给方法或类打自定义标签再反射获取
  4. SQL Cookbook—查询、排序
  5. mybatis 批量增加 Parameter &#39;__frch_item_0&#39; not found. Available parameters are [list]
  6. Django 入门项目案例开发（下）——创建项目应用及模型类
  7. MySQL之存储引擎（表类型）的选择
  8. File.Exists(Application.StartupPath + \\Settings\\Settings.xml)
  9. 【tomcat资源映射本地路径配置】
  10. Java并发编程之volatile关键字解析