Searching algorithm with complexity O(log n), UNSORTED list/array

Question

I had this exercice in an exam which stated:

Find an algorithm which can search for the highest number in an unsorted list and have a Big-Oh complexity of O(log(N)).

The only searching algorithm with a log n complexity that I have found is the binary search algorithm but that one requires my list/array to be sorted.

Is there such an algorithm?

Answer 1

This is a trick question. It has not been stated that the list has N elements. So, you can use a change of variable, and replace N with 2^K. Now, solve the problem with a linear algorithm on a list with K elements.

If we assume there are N elements in the list, a possible solution would be to use N parallel computing elements [ CE₀ .. CE_N ]. In the base case of the algorithm, we let each computing element CE_i in [ CE_N/2 .. CE_N ] compare list values x_2i-N and x_2i-N+1. Each computing element reports the larger of their two assigned values to CE_i/2. The iterative steps of the algorithm is that each computing element CE_k that receives two reported values reports the largest to CE_k/2. This iterative logic continues until CE₀ processes a report from itself. Instead of reporting to itself again, it outputs the result.

If parallel computation is ruled out, then there is no solution to the problem.