pg – IT汇

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

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

Using binary search with a little bit change.
time complexity: O(log n)
The force brute way: O(n)

int findMaximum(vector<int>& array){
    int i = 0;
    int j = array.size()-1;
    while(i <= j){
        if(i == j)
            return array[i];
        if(i == j-1)
            return array[i] > array[j] ? array[i] : array[j];
        int mid = i + (j-i)/2;
        if(mid-1 >= 0 && mid+1 < array.size()){
            if(array[mid] > array[mid-1] && array[mid] > array[mid+1])
                return array[mid];
            else if(array[mid] > array[mid-1] && array[mid] < array[mid+1])
                i = mid + 1;
            else if(array[mid] < array[mid-1] && array[mid+1] < array[mid])
                j = mid-1;
        }
    }
    return -1;
}

pg

近期文章

近期评论

标签

热门

文章归档

分类目录

功能