Efficient way to find the maximum number in an array

Question

This is an interview question. There is an array of integers. Array elements can follow the following patterns.

• numbers in ascending order
• numbers are in descending order.
• the number increases at the beginning and decreases at the end
• the number decreases at the beginning and increases at the end

What is an efficient way to find the maximum number in an array?

Answer 1

In this case, all you have to do is determine if it is (3). If not, the answer will be max (first, last).

In the case when all the elements are equal, you will need to completely look for the array to show that there is not a single large number somewhere in the middle. Therefore, I think O (n) determine whether you are in (3).

Answer 2

Ok anyway you have

• The last number.
• First number.
• Moving from start to finish, stopping at the first descent and printing the previous number.
• Compare the first and last numbers.

If you don’t know what case you are in, then you can check this when searching for max by doing the following (in the C-like pseudocode):

for (int i=0; i<end; ++i) { if (array[i] < array[i+1]) { // CASE 1 or 3 for (int j=i+1; j<end; ++j) { if (array[j] > array[j+1]) { // CASE 3 return array[j]; } } // CASE 1 return array[end]; } } // CASE 2 or 4 return max(array[0],array[end]); 

Answer 3

You can determine with the type of array by checking the first two and last two elements

• This is the last element.
• This is the first element.
• see below
• It is more of the first and last elements

For 3, start by looking at two elements in the middle of the array, if they are still increasing, max is greater in the array, if they are decreasing, max is less in the array. Repeat in binary search

Answer 4

Since cases 1-3 have one peak (a value surrounded on both sides by values ​​below itself or the edge of the array), and case 4 has two peaks at both ends of the array, this problem can be solved simply in O(log n) time for all cases:

First apply the 1D peak search algorithm to find the peak in the array.

If the peak occurs in the middle of the array (not in the first or last position), then this is case No. 3, and the peak is also maximum.

If the peak is the first or last element of the array, then this is one of the cases 1, 2 or 4, and the max array is the maximum (first, last).

Python-esque pseudo-code:

 def find-peak(list): mid=len(list)/2 if (list[mid-1] > list[mid]: return find-peak(list[:mid-1]) else if (list[mid+1] > list[mid]: return find-peak(list[mid+1:]) else: return mid def find-max(list): peak = find-peak(list) if peak==0 or peak==len(list)-1: return max(list[0], list[-1]) else: return list[peak] 

Answer 5

1. last number 2. first number 3.do binary-like search, select pivot point, calculate the slope, just to decide to go left or right 4. first or last number

Answer 6

The method for identifying four cases is straight forward, assuming that the sequence does not have a repeating number:

 case 1: arr[0] < arr[1] && arr[end-1] < arr[end] case 2: arr[0] > arr[1] && arr[end-1] > arr[end] case 3: arr[0] < arr[1] && arr[end-1] > arr[end] case 4: arr[0] > arr[1] && arr[end-1] < arr[end] 

As mentioned in other answers, the way to find max is also straightforward:

 case 1: arr[end] case 2: arr[0] case 3: binary search, until found n that arr[n-1] < arr[n] > arr[n+1] case 4: max(arr[0],arr[end]) 

Answer 7

The answer depends on what is meant by "efficiency." If you need fast code, look at someone else. If you want to be effective as a programmer, you probably should just use a library call (e.g. max_element() in C ++.)

Answer 8

This problem reminds me of the Golden Algorithm for finding the minimum of a unimodular (i.e.: decreasing, then increasing) function. This is a kind of binary search version that calculates the value of a function (for example: checks an array) as few points as possible.

Now you need to translate it into a discrete version and add additional whistles to determine if the function is concave or convex.