852. Peak index of the mountain array

This is the sixth day of my participation in Gwen Challenge

The title

Source: LeetCode

Link: leetcode-cn.com/problems/pe…

An array ARR that matches the following properties is called a mountain array:

  • arr.length >= 3

  • There exists I (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]

    Give you a range array of integers arr, return anything that satisfies arr[0] < ARr [1] <… arr[i – 1] < arr[i] > arr[i + 1] > … > arr[arr.length-1] subscript I.

Example 1:

Input: arr = [0,1,0] output: 1Copy the code

Example 2:

Input: arr = [0,2,1,0Copy the code

Example 3:

Arr = [0,10,5,2] output: 1Copy the code

Example 4:

Input: arr = [3,4,5,1Copy the code

Example 5:

Input: arr =,69,100,99,79,78,67,36,26,19 [24] output: 2Copy the code

Tip:

  • 3 <= arr.length <= 104
  • 0 <= arr[i] <= 106
  • Subject data guaranteearrIt’s an array of mountains

** Advanced: ** It is easy to think of time complexity O(n) solutions, can you design an O(log(n)) solution?

Problem analysis

The mountain array means that if there is a maximum value in an array, subscript I, then the array is increasing up to I, and decreasing after I

The next step is to design an O(log(n)) solution, and when you see O(log(n)), you naturally think of binary search

A traversal

This is a very conventional solution, which is to go through the array once, find the ith element, arr[I]> arr[I -1] and arr[I] < arr[I +1], then I is the result to return, and I will not write the code

Binary search

To prevent overflow when calculating mid, it is recommended to write mid = left + (right-left) / 2

I think it’s better if I write mid = (left + right) >>> 1

public class Solution {
  public int peakIndexInMountainArray1(int[] arr) {
    // Select * from [1,arr. Length-2]
    int left = 1;
    int right = arr.length - 2;
    while (left <= right) {
      int mid = (left + right) >>> 1;
      if (arr[mid] < arr[mid - 1]) {
        right = mid - 1;
      } else if (arr[mid] < arr[mid + 1]) {
        left = mid + 1;
      } else {
        returnmid; }}return -1; }}Copy the code

The idea of binary search is very simple, but the code is still very prone to error, is really the idea is very simple, details are the devil

  • First I define left = 1, right = arr. Length-2, this is because according to the problem, the array must have at least three numbers, and the peak is not the 0 or the last digit. This definition means that the interval I’m looking for is a closed interval [1,arr. Length-2]
  • Because left and right are closed intervals, the while loop uses less than or equal to, not less than. For example, if there are only three numbers in the array {1, 2, 3}, and left=1, right=1, you can’t enter the while loop if you use less than
  • Right = mid – 1, left = mid + 1, not right = mid, left = mid. That is, mid is in the closed interval, and we’ve already computed it once, so we’re going to get rid of it next time

So we could also write it like this

class Solution {
  public int peakIndexInMountainArray(int[] arr) {
   int left = 1;
    int right = arr.length - 1;
    while (left < right) {
      int mid = (left + right) >>> 1;
      if (arr[mid] < arr[mid - 1]) {
        right = mid ;
      } else if (arr[mid] < arr[mid + 1]) {
        left = mid + 1;
      } else {
        returnmid; }}return -1; }}Copy the code

Details about binary search can see, a binary search algorithm is www.cnblogs.com/kyoner/p/11…

Leetcode also summarizes three templates for binary lookup leetcode-cn.com/leetbook/re… You can see