Binary search on unsorted arrays?

I came across this开发者_如何学C 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 ?

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.

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 !!

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