[数据结构与算法]LeetCode每日一题(852. Peak Index in a Mountain Array)

An array arr a mountain if the following properties hold:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < … < arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

Constraints:

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• arr is guaranteed to be a mountain array.

二分搜索， 一共就三种情况:

1. left < middle < right
2. left < midele > right
3. left > middle > right

情况 1， 3， 我们只需要往大的方向去找即可， 情况 2，我们要对比左半部分和右半部分的值，取大的即可。注意两部分对比的时候要包括中间点的值， 调试的时候发现的， 至于为什么，现在也没想明白

impl Solution {
    fn bisearch(arr: &Vec<i32>, l: usize, r: usize) -> usize {
        if l == r {
            return l;
        }
        let m = (l + r) / 2;
        if arr[m] > arr[l] && arr[m] > arr[r] {
            let left = Solution::bisearch(arr, l, m);
            let right = Solution::bisearch(arr, m + 1, r);
            let max = arr[m].max(arr[left]).max(arr[right]);
            if max == arr[m] {
                return m;
            }
            if max == arr[left] {
                return left;
            }
            return right;
        }
        if arr[l] < arr[m] && arr[m] < arr[r] {
            return Solution::bisearch(arr, m, r);
        }
        Solution::bisearch(arr, l, m)
    }
    pub fn peak_index_in_mountain_array(arr: Vec<i32>) -> i32 {
        Solution::bisearch(&arr, 0, arr.len() - 1) as i32
    }
}