【LintCode-二分搜索】159. Find Minimum in Rotated Sorted Array

lintcode 159. Find Minimum in Rotated Sorted Array

url: https://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array/description

1、题目

Description
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.
Example

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

2、思路

经典的二分搜索，但是这次是把中间元素与边界元素进行比较

3、python代码实现

# -*- coding: utf-8 -*-
class Solution:
    """
    @param nums: a rotated sorted array
    @return: the minimum number in the array
    """

    def findMin(self, nums):
        if not nums:
            return -1

        head = 0
        tail = len(nums) - 1
        length = tail
        while head < tail:
            mid = head + (tail - head) // 2
            if nums[mid] > nums[tail]:
                if nums[mid] > nums[mid + 1]:
                    return nums[mid + 1]
                head = mid + 1
            else:
                if nums[mid] < nums[mid - 1]:
                    return nums[mid]
                tail = mid - 1
        return nums[0]


if __name__ == '__main__':
    s = Solution()
    print(s.findMin([4, 5, 6, 7, 0, 1, 2]))
    print(s.findMin([6, 1, 2, 3, 4, 5]))
    print(s.findMin([4, 1, 2]))
    print(s.findMin([4, 0]))
    print(s.findMin([1]))