Thread: finding the largest number in a binary search

It is possible to attempt to perform a binary search on an array that might not be sorted, in a useful manner. I did this myself in my implenentation of an algorithm I called "Hopeful Search", listed on my webpage (See my sig). Basically you go about your way performing a recursive binary search as usual, then for any recursive call that fails to find the item, you do a recursive call on the other half anyway.

1. If the array IS sorted and the item IS in the array then it takes O(log n) time.
2. If the item is not in the array then it searches the whole array taking O(n) time.
3. If the array is not sorted, then it takes O(n) time though it can often be quicker particularly if the array is partially sorted.

This is of course much more useful if you know in advance that the item you are searching for is always in there.
Nifty huh?!

Originally Posted by iMalc

Nifty huh?!

Not really, it's no better than a sequential search, which is way easier to program. Actually it's probably worse due to overhead in maintaining the "splits" of the binary search when the value doesn't fall into the half you are searching first.

It all depends on how likely the list is to be sorted. If it is sorted 90% of the time and the item is always present then of course it is going to be faster than a linear scan.

Originally Posted by iMalc

It all depends on how likely the list is to be sorted. If it is sorted 90% of the time and the item is always present then of course it is going to be faster than a linear scan.

I guess it's easy to make your algorithm optimal when you first set up all the confining conditions.

My linear search routine is always faster when the item searched for is in the first few elements which is 90% of the time.


Seriously, if you have a list that is sometimes sorted and sometimes not, it would probably just be easier to sort it the 10% of the time when it's not sorted than trying to do a pseudo binary sort on an unsorted list. And now since you are routinely keeping it sorted, it won't even be 10%

Sure, I agree. I'm not trying to twist any old problem into one that would specifically suit this particular algorithm as a solution though. I'm just saying that most unusual algorithms out there can be the optimal solution in some real-world scenario. I would never twist a problem to fit a specific solution. Nor would I make it out to be any more useful than it is, the algorithm is most of the time completely pointless, but it was relevant to the discussion.

For example:
A part of your program interoperates with a 3rd party library. That library may provides as output to some function, an array of items that is sorted using a sorting algorithm that has a tiny bug which of course you cannot fix as the company has gone bust or whatever. The bug is no more serious than causing a few items to occasionally be out of order though. You are not able to sort the array correctly before searching because the library also has pointers to some of the items and will fail if those items are moved, and because you only need to perform a small number of searches before a new array is returned anyway and sorting would add too much time. Thus you must treat it as read-only. You also happen to know that by the very nature of the particluar problem, that the item you are searching for is always in the array. The array is very large and you do not have time to spend searching through on average half the items each time as with a sequential search, however the occasional slow search here and there is okay since that slowdown is amortised out.

Now I'm not saying that one would ever intentionally create such a scenario. I'm saying that if one were faced with such a scenario, it would be in your best interests to be able to adapt and come up with a creative solution which would quite possibly match the algorithm I described.