Finding the minimum in an unsorted array in logarithmic time

Question

Is there an algorithmic approach to find the minimum of an unsorted array in logarithmic time ( O(logn) )? Or is it only possible in linear time? I don't want to go parallel.

Thanks

Michael

Solution 1

If the list is unsorted, your search has to be at least linear. You must look at each item at least once, because anything you haven't looked at might be less than what you've already seen.

Solution 2

Going parallel wouldn't help in general. If you have more processors than n, and you don't count the time it takes to load the data, which is O(n), then yes, you can do it in logarithmic time. But suppose you have, say, 10 numbers per processor. It takes a certain amount of time. Now make it 20 numbers per processor. Each processor will take twice as long to crunch its numbers, before they compare each other's results in parallel. O(n) + O(log n) = O(n).

Solution 3

It is not possibly in linear time, because in lg n steps you can only inspect lg n elements, and because they are unsorted, the values carry no information about other values in the array.