I came across a question in an interview two days ago regarding the optimal finding of the maximum element in an array, and I have a query regarding this.
The array described by the interviewer consists of integer values that can be repeated (not necessarily in consecutive places), and also consists of two parts (one part may be empty): the first part in decreasing order and the second part in non-decreasing order, t .e. if a [n] is an array of n integer values, then a [i] <= a [i + 1], I in [1, m] and a [j]> = a [j + 1], j in [m, n] and m lies somewhere between 1 and n inclusive. Now they asked me to find the maximum value in the array .
I have argued that since some elements can be repeated, I cannot isolate the search space using the split and conquer strategy. If all the elements were different, we could find the maximum lg n times using binary search. But there is at least one input sequence (possibly when all the elements are the same) for which we must at least have an n-1 comparison before we can determine which element is maximal.
The interviewer asked me to think about whether I could put some kind of restriction on the input so that the problem could be solved lg n times. At that time I could not decide and still think.
It would be helpful if you could help me with my thoughts.
source
share