Find Maximum in Increasing and Decreasing Array

Interview

Geeks

Description:

Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array.

Example:

Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}
Output: 500

Input: arr[] = {1, 3, 50, 10, 9, 7, 6}
Output: 50

Corner case (No decreasing part)
Input: arr[] = {10, 20, 30, 40, 50}
Output: 50

Corner case (No increasing part)
Input: arr[] = {120, 100, 80, 20, 0}
Output: 120

Idea:

类似binary search，O(lg n). Check arr[mid] vs arr[mid-1] and arr[mid+1]大小关系。

考虑到只有increase，和decrease的情况。以及只有两个number的情况。

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int maxInIncreaseDecrease(vector<int> arr){
    int intMin=numeric_limits<int>::min();
    if( arr.size()==1)
        return arr[0];
    else if(arr.size()==2){
        return max(arr[0], arr[1]);
    }
    int begin=0;
    int end=arr.size()-1;
    int mid;
    while(begin<=end){
        mid = begin+(end-begin)/2;
        if(mid==0){
            return arr[0]>=arr[1] ? arr[0]:intMin;
        }
        else if(mid==arr.size()-1){
            return arr[arr.size()-1]>=arr[arr.size()-2] ? arr[arr.size()-1]:intMin;
        }
        else if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]){
            return arr[mid];
        }
        else if(arr[mid]<=arr[mid-1]&&arr[mid]>=arr[mid+1]){
            end=mid-1;
        }
        else{
            begin=mid+1;
        }
    }
    return arr[mid];
}

int main(){
    vector<int> arr={120, 100, 80, 20, 0};

    cout<<maxInIncreaseDecrease(arr);
}