在数组中找到一个局部最小的位置

题目

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0] < arr[1]，那么arr[0]是局部最小；如果arr[N-1] < arr[N-2]，那么arr[N-1]是局部最小；如果 0 < i < N-1，既有 arr[i] < arr[i-1]，又有arr[i] < arr[i+1]，那么arr[i]是局部最小。

给定无序数组arr，已知arr中任意两个相邻的数都不相等。写一个函数，只返回arr中任意一个局部最小出现的位置即可。

基本思路

本题可以使用二分查找做到时间复杂度O(logN)，空间复杂度O(1)，具体步骤如下：

如果arr长度为1或者，arr[0] < arr[1]，返回0；如果arr[N-1] < arr[N-2]，返回N-1

如果arr长度大于2且arr的左右两头都不是局部最小，令left = 1，right = N-2，然后开始二分查找：

（1）令 mid = (left + right) // 2

（2）如果arr[mid] > arr[mid-1]，可知在arr[left…mid-1]上肯定存在局部最小值，令right = mid - 1

（3）如果arr[mid] > arr[mid+1]，可知在arr[mid+1…right]上肯定存在局部最小值，令left = mid + 1

（4）如果不满足（2）和（3），则mid本身就是局部最小，返回mid即可

（5）重复二分查找步骤，直到left > right

def lessMinLocal(L):if L == None or len(L) == 0:return -1if len(L) == 1 or L[0] < L[1]:return 0if L[len(L)-1] < L[len(L)-2]:return 1left = 1right = len(L)-2mid = 0while left < right:mid = (left + right)/2if L[mid] > L[mid-1]:right = mid - 1elif L[mid] > L[mid+1]:left = mid + 1else:return midreturn left