If array needs to be sorted would it count as part of the binary search algorithm

Question

I am trying to understand the speed of the Binary Search algorithm. I understand it needs to operate on a sorted array. However if the array comes in unsorted and performing the sorting. Wouldn't the sorting be part of the Binary Search and thus its performance would be slower?

I am confused because I think that there is very little chance to use this algorithm if the data does not come in sorted. And if my code needs to sort it then why isn't it counting towards the search algorithm.

Sorry if I am confusing, Thank you for helping.

Answer 1

You can't just point at an algorithm and say: It's got O(n^2) complexity!

That's what people usually say, sure. But that's shorthand. They're omitting things; assuming that the listener / reader will make assumptions.

You need to fully describe the exact algorithm, the conditions under which it is applied, and the precise definition of n and any other variable.

Then, you can answer that question. The problem you're having here is that the definition of 'what is the performance of binary search' is unclear. If you assume it means X whilst your buddy assumes it means Y, and you then argue about the answers, you're not actually having a constructive debate at all. You're just tilting at windmills; the real problem is that neither of you figured out the problem is communicating the basics.

Given that there is some confusion here, I'll give you 3 different more or less equally sensible more fleshed out definitions, along with the actual answer for each such definition. Hint, for one of them, 'binary search' isn't the fastest algorithm!

Given [1] a list that is already sorted, and [2] a single value, write me an algorithm that determines if this value is in the list or not.

The best answer would be: A binary sort algorithm, and its complexity would be O(log n).

Given [1] a list that is not sorted, and [2] a single value, write me an algorithm that determines if this value is in the list or not.

The best answer would be: Just iterate through the list. Its complexity would be O(n), and binary sort is not part of this answer at all.

given [1] a list that is not sorted, and [2] a list of tests, whereby each individual test is defined by a single value, but they all use the same input unsorted list, write an algorithm that will, for each test, determine if the value for that test is in the list or not, and then give me the amortized complexity (basically, the complexity of the whole thing, divided by the # of tests we ran).

Then the best answer would be: First sort the list, spending O(n log n) time to do so, but we get to amortize that over the test case count, and then use binary search for each individual test, adding an O(log n) complexity to each test. If we term n the size of the input list and t the number of tests we have, this gets us:

O( (n log n)/t + O(log n) )

Which is the actual answer to the question, complex as it may look. But, if t is large or even considered effectively infinite in size, OR we add one more rider to the question:

The list from [1] is given to you in advance and, within reasonable time and memory limits, you may preprocess this data without needing to amortize these costs across your test cases

then that boils down to just O(log n), as the large value for t makes that (n log n) / t factor approach zero.

In communicating this to your buddy, given that we don't talk in entire scientific papers, one might then say: "The algorithmic complexity of the binary sort algorithm is O(log n)", even if that omits a gigantic chunk of the full story.

You interpret the question as per the second case (input is unsorted, the input comprises both the list and the value to search for, no multi-test clause). Someone who says 'binary search is O(log n)' is labouring under either the first or third. You're both right.

NB: The third definition seems unusually complicated. However, it matches common scenarios. For example, 'we have compiled a list of folks living in town and their phone numbers, and we want to print them in a giant book with the aim of letting recipients of this book look up phone numbers. We expect over the lifetime of a single print run that the 100,000 citizens of the township will eaech do on average about 50 lookups, for a grand total of 5 million lookups for this single list. That gives you t= 5 million, n = 200,000 (let's say 200k people live here, half of which get a phonebook). Plug those numbers in and sorting the phonebook wins by a landslide vs. releasing the phonebook in arbitrary, unsorted order. Even if, yes, you start 'down' the effort of sorting it and won't make up for that loss until a few folks have speedily looked up a few phone numbers to make up for your efforts in sorting it before printing the book.

Answer 2

Yes. If

• the data comes in unsorted
• you only need to search for one element

...then you would have to first sort the data to use binary search, which would take a total of O(n log n + log n) = O(n log n) time.

But once the data is sorted, you can then binary search on that data as many times as you want. You don't have to sort it again each time.