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

一、题目

定义局部最小的概念。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 中任意一个局部最小出现的位置即可。

二、思路

首先把几个极端条件列举出来给 pass 掉。当数组为空时，直接返回 -1；如果数组中只有一个数时，直接返回 0 位置；然后判断数组的最左边，如果 arr[0] < arr[1] 时，返回位置 0 即可；接下来判断数组的最右边，如果 arr[N-1] > arr[N-2]，返回位置 N-2 即可。

这时，一定存在局部最小值，因此通过 arr[0] < arr[1] 和 arr[N-1] > arr[N-2] 这两个条件不成立，就已经证明了数组不是有序的。所以一定存在局部最小值。

对于其他平常情况，我们采用二分查找的办法。定义 left 为 1，right 为 N-2；因为位置 0 和位置 N-1 位置都已经尝试过了。遍历数组，条件是 left < right，取 mid = left + (right-left) / 2，当 arr[mid] > arr[mid-1] 时，说明左边肯定有局部最小值，让 right = mid-1，然后遍历左边子数组。当 arr[mid] > arr[mid+1] 时，说明右边肯定有局部最小值，让 left = mid+1。当这两个条件都不满足的时候，说明 mid 就是局部最小值的位置，直接返回 mid 位置即可。

一直遍历，知道 left == right 时结束，返回 left 即可。因为一定存在局部最小值。

三、代码

#include <vector>
#include <iostream>

class Solution {
public:
    int get_less_index(const std::vector<int>& arr) {
        // arr 为空
        if (arr.empty()) {
            return -1;
        }
        // arr 只有一个值
        if (arr.size() == 1) {
            return 0;
        }
        // 判断最左边或者最右边，如果有局部最小，直接返回即可
        if (arr[0] < arr[1]) {
            return 0;
        }
        int count = arr.size();
        if (arr[count-2] > arr[count-1]) {
            return count-1;
        }
        // 二分查找
        int left = 1, right = count-2;
        for (; left < right;) {
            int mid = left + (right-left) / 2;
            if (mid-1 >= 0 && arr[mid] > arr[mid-1]) {
                right = mid - 1;
            } else if (mid+1 <= count && arr[mid] > arr[mid+1]) {
                left = mid+1;
            } else {
                return mid;
            }
        }
        return left;
    }
};

int main() {
    Solution s;
    std::vector<int> arr{5, 4, 0, 9, 21, 3, 10};
    auto res = s.get_less_index(arr);
    std::cout << res << std::endl;
    return 0;
}