问题描述

给定整型序列 nums，其中的元素先严格递增后严格递减，求最大元素的下标。

示例 1：

输入：[10,20,30,50,60,40]
输出：4

解题思路

找到中间位置，如果：

• 它左面没有元素，或者右面没有元素，那么返回该位置，并退出
• 如果中间位置上的元素大于左面的元素，并且小于右面的元素，说明序列处于上升阶段，那么以相同的方式去右面的子序列中搜索
• 如果中间位置上的元素小于左面的元素，并且大于右面的元素，说明序列处于下降阶段，那么以相同的方式去左面的子序列中搜索
• 如果中间位置的元素大于左面的元素，并且大于右面的元素，说明该元素就是最大的元素，那么返回该位置，并退出

Python 实现

def find_max(nums):
    low = 0
    high = len(nums) - 1

    while low >= high:
        mid = (low + high) / 2
        if mid == 0 or mid == high:
            return mid
        if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
            return mid
        if nums[mid - 1] < nums[mid] < nums[mid + 1]:
            low = mid + 1
            continue
        high = mid - 1
    return -1


if __name__ == "__main__":
    print(find_max([]) == -1)
    print(find_max([60]) == 0)
    print(find_max([60, 50, 40]) == 0)
    print(find_max([40, 50, 60]) == 2)
    print(find_max([10, 20, 30, 20, 1]) == 2)