卖萌的弱渣

I am stupid, I am hungry.

Find Minimum in Rotated Sorted Array

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.

Example

Given [4, 5, 6, 7, 0, 1, 2] return 0

Note

You may assume no duplicate exists in the array.

Solution

  • 数组可以看成是两个ordered subarray 组成
  • 前面那个subarray的任意值都比后面那个大
  • 最小值一定在后面那个sub array中
  • 如果num[front] > num[end]， 那么没有找到有序的sub array, 后移front
  • 反之，则在sub array中，找最小值
(Find-Minimum-in-Rotated-Array.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    # @param num: a rotated sorted array
    # @return: the minimum number in the array
    def findMin(self, num):
        # write your code here
        if num == None or len(num) == 0:
            return 0
        front = 0
        end = len(num)-1

        result = sys.maxint
        while front <= end and front >=0:
            mid = (front+end)/2
            # case 1: no in orded subarray
            if num[front] > num[end] :
                front = mid+1
            else:
                # case 2: already in a orded subarray, search for the lowest value
                if result > num[front]:
                    result = num[front]
                front -= 1
                end = mid - 1

        return result