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 ?
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.
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag. I m trying to figure out how I would find the "spin" of a sphere of a ...
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7. There s some documentation and a tiny Wikipedia ...
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#. Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is ...
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...
