An array is in ascending order and then descending in order to find the maximum value with the optimal time complexity. For example, [1, 2, 2, 2, 2, 2, 2, 3, 1]

an array is in ascending order and then descending in order to find the maximum value. For example, [1, 2, 2, 2, 2, 2, 2, 3, 1], using the optimal time complexity, the algorithm achieves the maximum value 3

.
Java cPP
Sep.30,2021 
/**
 * 
 * @param arr : 
 * @param low : 
 * @param high: 
 * @return    : 
 */
public static int getMax(int[] arr, int low, int high) {
   
    while (low < high) 
    {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > arr[mid + 1]) {
            high = mid;
        } 
        else if (arr[mid] < arr[mid + 1])  {
            low = mid + 1;
        }
        else  //arr[mid]arr[mid+1]
        {                
            if (mid-1 >= low) //  [low~high]
            {
                if(arr[mid-1] > arr[mid])
                {
                    high = mid-1;
                }
                else if(arr[mid-1] < arr[mid])
                {
                    low = mid+1;
                }
                else //arr[mid-1]  arr[mid]  arr[mid-1]arr[mid],arr[mid+1]  
                    //midmidmidmid
                    //
                {
                    int one = getMax(arr, low, mid-1);
                    int two = getMax(arr, mid+1, high);
                    
                    return one > two ? one : two;
                }
            }
            else { // mid-1 < low  midlowarr[low] == arr[high]
                return arr[low];
            }
        }
    }
    
    return arr[low];
}

= update
Recursion and array copy are removed, and the return value of the function is changed to index to facilitate the handling of empty arrays 

  
 Thank you for the same problem

Previous: React dynamic brush elements

Next: Vue modifies the content of an input box and then clicks cancel to get the original content.

css mysql arrays josn react html typescript webpack npm sass R objective-c .net sql-server jquery python-3.x angularjs django angular excel regex iphone ajax linux xml pandas vba spring database wordpress string wpf xcode windows bash postgresql oracle multithreading eclipse list firebase algorithm macos forms image scala visual-studio azure bootstrap spring-boot react-native python-2.7 docker performance function winforms matlab powershell apache dataframe api sqlite numpy rest shell selenium flutter dart maven loops qt swing android-studio csv express file class tensorflow sorting codeigniter perl
© 2021 CodesHelper
Advertising Contact us About us
Menu