CODEWITHSUNDEEP
arraysalgorithmsearchcomplexity-theory
user3903577
user3903577

Reputation: 63

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

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?

Upvotes: 5

Views: 22322

Answers (4)

Ethan
Ethan

Reputation: 41

Ik this is very old, but if I had this question, I would have used the fact that it did not specify that the list is N elements long, meaning it’s valid to make the assumption that the list has 1 element, then a simple line of code like this should work giving you O(1) time complexity,

Answer= list[0]

Upvotes: 0

jxh
jxh

Reputation: 70402

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 2K. 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 [ CE0 .. CEN ]. In the base case of the algorithm, we let each computing element CEi in [ CEN/2 .. CEN ] compare list values x2i-N and x2i-N+1. Each computing element reports the larger of their two assigned values to CEi/2. The iterative steps of the algorithm is that each computing element CEk that receives two reported values reports the largest to CEk/2. This iterative logic continues until CE0 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.

Upvotes: 13

vvv
vvv

Reputation: 53

The best one can do is O(n) time in an unsorted array.

But instead of simply looking through the whole list you can apply a partition() routine (from the quicksort algorithm) and instead of recursing on the lower half of the partition you can recurse on the upper half and keep partitioning until the largest element is found. This takes O(n) time.

Check out for detailed explanation:

http://en.wikipedia.org/wiki/Quickselect

How to find the kth largest element in an unsorted array of length n in O(n)?

Hope it helped! :)

Upvotes: 2

Gabz
Gabz

Reputation: 134

No, there is no such algorithms. In a unsorted list, find a highest number require to browse through all elements.

So, no algorithm better than O(n) exists!

Upvotes: 2

Related Questions