Binary search on unsorted arrays?

Question

I came across this document Binary Search Revisited where the authors have proved/explained that binary search can be used for unsorted arrays (lists) as well. I haven't grokked much of the document on a first reading.

Have any of you already explored this ?

Caruthers

Hm, haven't read it yet, but currently I don't see how this could work for unsorted arrays (of course, the sorting could be done with a function, but it would still be sorted). – Matrimony

I'm pretty sure this is a hoax. Finding something in an unsorted list will always be a O(n) problem, at least within the current laws of the universe. – Dear

Of course you can do a binary search on an unsorted array. The question remains whether you will find what you are looking for :-) – Galitea

Since the definition of binary search contains the fact that its input must be sorted, this is not binary search. It may be "binary search" like, but it's not binary search. See en.wikipedia.org/wiki/Binary_search_algorithm, but there are thousands of other places you will find the same definition. – Hersch

@Philippe The current laws of the Universe allow you to find it in Log(n) if you recursively partition the appropriate part of the array. It's pretty cool, sort of applying "half a quicksort". A bit too long to explain in a comment, though. See Cormen (Medians and order statistics). – Loutish

@Fernando: No way. Finding an item in an unsorted list can never be done in O(log N) time. If you're so sure, why don't you write a minimal sample application that demonstrates it? – Dear

@Philippe Just to make sure we're on the same page: it's possible to find the k-th smallest (or biggest) element in an unsorted array in O(Log n) time. I'm not saying that you can find an arbitrary element in O(Log n). I'll post code for the former later. – Loutish

Answer 1

I've just read the paper. To me the author uses the term binary search to address the Bisection method used to find the zeros of a continuous function.

The examples in the paper are clearly inspired to problems like find the zero into an interval (with translation on the y axe) or find the max/min of a function in tabular data.

The arrays the essay consider are not random filled ones, you will find a rule to construct them (it is the rule tied to the function used to dump them)

Said that it is a good chance of tinkering about different algorithms belonging to a common family in order to find similarity and differences. A good chance to expand your experiences.

Definitely not a new concept or an undervalued one.

Teatime

Answer 2

Lookin for 3 into that unsorted list with binary or bisection :

L = 1 5 2 9 38 11 3

1-Take mid point in the whole list L : 9 3 < 9 so delete the right part of the list (38 11 3) here you can already understand you will never find 3

2-Take mid point in the remaining list 1 5 2 : 5 3 > 5 so delete the right part of the list (5 2) remains 1

Result : 3 unfound

Two remarks:

1-the binary or bisection algorithm consider right and left as an indication of the order So i have rudely applied the usual algo considering right is high and left is low If you consieder the opposit, ie right is low and left is high, then, trying to find 3 in this slighty similar list will lead to " 3 unfound" L' = L = 1 5 2 9 3 38 11 3 < 9 / take right part : 3 38 11 mid point 38 3 < 38 take right part : 11 3 unfound

2- if you accept to re apply systematicly the algorithm on the dropped part of the list than it leads to searching the element in a list of n elements Complexity will be O(n) exactly the same as running all the list from beg to end to search your value. The time of search could be slightly shorter. Why ? let's consider you look one by one from beg. to end for the value 100000 in a sorted list. You will find it at the end of your list ! :-)

If now this list is unorderd and your value 100000 is for example exactly at the mid point ... bingo !!

Salesmanship

Answer 3

Binary Search can be implemented on a rotated unsorted array/list.

Askwith

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Returnee