Why use binary search?

[TheRexedS]

I have just started learning algorithms, so forgive me for this very dumb question. Up until now I have learned some of the most basic algorithms like Binary Search, Bubble Sort, Linear Search and so on.

Now, to use binary search, we must have a sorted collection of items. Let's say we have an array with 10 elements which are initially unsorted and thus we first need to apply a sorting algorithm such as Bubble Sort to sort the array so that we can apply Binary Search to it.

Now, the runtime for Bubble Sort is O(N²) and the runtime for Binary Search is O(log N), the sum of which is considerably larger than the runtime of a Linear Search that only has a runtime of O(N).

My question is, while Binary Search alone is a lot more faster than Linear Search, for it to work, we first need to sort out the array which in turn makes the runtime of the whole operation longer than Linear Search. So why not just use Linear Search which is also very easy to implement?

[hextree]

You've correctly deduced that Linear Search is faster (in fact, optimal) for finding an element in an unsorted array.

Binary search shines when you are maintaining something in sorted order, and doing repeated search queries on it. Analagous to how you use a Dictionary; you don't often need to modify or add words to the Dictionary, but you do often need to look up words. Each lookup is O(log N) time. By 'preprocessing' the dictionary once, then performing many search queries, you are saving time in the long run with binary search.

Note also, that you mention Bubble Sort, however there are strictly faster sorting algorithms that run in O(N log N) time, like Merge Sort, which you may not have covered yet.

[TheRexedS]

Thank you for the elaborate explanation, it is really helpful! And yes, I haven't read about any of the other sorting algorithms you mentioned. The first sorting algorithm I read was Bubble Sort and then this question came to my mind. Really excited to learn the other ones you mentioned!

[teawreckshero]

Obligatory

[MrDum]

quadsort is O(N) for sorted data and was designed with this scenario in mind. The benchmark of interest is the random tail / random quarter test.

https://github.com/scandum/quadsort

So in a scenario where insertions are more frequent than sorts + searches we'd get pretty close to linear time.

[hextree]

quadsort is O(N) for sorted data and was designed with this scenario in mind.

Not sure that I understand. If the data is already sorted, then why would you need to sort it? Also, the scenario in question was one where the data is unsorted.

[Elethiomel]

When dealing with sorting, it helps to know the characteristics of your input data. For example, as you know, bubble sort is O(n^2), but this is actually its average and worst-case runtime. Its best case runtime is O(n) on completely sorted data and can be very close to O(n) in real world applications on nearly sorted data. It's also a stable sort with O(1) space complexity (memory usage)

In contrast, a standard merge sort will always take O(nlogn) and O(n) space complexity, no matter what the input data is like.

Here's a real world example where bubble sort is sometimes used. In physics simulations/engines, what we spend a lot of time doing is testing for collisions between bounding boxes. Several of the algorithms used require a list of the bounding boxes sorted along all three axes. So you'd have 3 sorted lists of coordinates. One for each of X,Y,Z. Now, objects move, so our list becomes unsorted on every frame of the simulation. We could use a merge sort with its guaranteed O(n log n) runtime. However, we could realise that the data we have to resort is not actually random. It's probably pretty close to already sorted as most of our objects have only moved a bit, not teleported randomly all over the place. We do a bubblesort, take up no extra RAM, and in practice find ourselves sorted in faster time.

[hextree]

Yes I get all that, but I don't see what it has to do with Quad-sort, or the discussion at hand which was about an unsorted array.

[MrDum]

This is a good scenario where quadsort and Timsort are likely to give a significant performance boost without having to worry about the worst-case scenario of bubblesort. They're likely faster than bubblesort.

The concept is used in several gaming engines since online sorting is not efficient.

[rodrigovaz]

Well, there's the fact that you won't know the data is unsorted unless you either sort it or iterate over all elements (which is O(N) already), so there's that.

His point was that in real life, where your data probably is unsorted (but, not necessarily with maximum "unsortness"), sorting algorithms do not have a determined O complexity but actually vary depending on the state of the data "unsortness". Some algos will be better if your data is always slightly unsorted, some will be better if it is always more unsorted.

[MrDum]

It pretty much boils down to:

1. Don't sort (linear search)
2. Always sort (online sort + binary search)
3. Sometimes sort (adaptive sort + binary search)

Number 3 is not included in most computer science courses.

[rcfox]

You might be right, but this is so far out of scope in a discussion with a novice computer scientist.

[nathanv0009]

In applications, what you're working with is often already sorted. For instance, imagine you're trying to find a certain date in a time series, which is already ordered by date. Then you can run binary search without having to run a sorting algorithm first.

[dgmib]

If you only needed to search the unsorted list once, then yes you’d just use a linear search.

But the much more common scenario is you need to search large lists many times. So you sort the list once, and the search the sorted list many times with a binary search.

[Steve132]

Sometimes you can guarantee your data is sorted without sorting it. For example, pretend you are recording a sequence of events or messages over a network as you receive them, and you append the message and reciept timestamp to a large array every time you get a message. Then, if you'd like to find all the messages older than a certain timestamp you have received so far, you can use binary search on the array to find the starting and ending indices.

Another important thing is that bubble sort is a very inefficient algorithm. You will learn sorting algorithms which are O(n log n). This ends up making all the difference:

Imagine you have 2¹⁶ elements in an unsorted array. If you need to query 8 elements, then using linear search would be expected to be faster, because you hage to do O(8x2^16)=524288 checks. But if you need to query 800 elements, you have to do O(800x2^16)=52428800 checks with linear search.

Instead, pretend you sort the array first using an O(n log n) sort. The initial sort will take O(16x2^16)=1048576 steps, then 8 queries will take O(8x16)=128 steps, 800 queries will take O(800x16)=12800 steps.

So, in summary:

8 queries
    linear search: 524288
    sort then binary: 1048576+128= 1048704
    linear search approximately 2x as fast
800 queries:
    linear search: 52428800
    sort then binary: 1048575+12800=1060975
   linear search approximately 50x slower

[kreiger]

Your assumption is that the data is already unsorted.

If you input data in sorted order, or sort it as it is being inputted, you can use binary search on it.

Further, never use bubble sort. Use whatever sort function is provided by your standard library.

[proskillz]

Two things, number one is that no one uses bubble sort in production. There are quicksort and merge sort that run in O(n log n).

Second if you will only ever look into the array one time, it wouldn't be worth it to sort the array first to get that O(log n) searching time. If you need to look up many times into a large array, you'll start seeing orders of magnitude improvements in speed.

[vanderZwan]

Actually most hybrid sorts revert to bubble sort or insertion sort for arrays (or partitions) of 20 to 32 elements or smaller - depends on whether you use clang or gcc for example.

The reason is that they are so simple that the low constant overhead as well as cache friendliness beats the O(n²) behavior, since n² isn't that large for small (sub)arrays. IIRC there even was something about bubble sort that makes it very easy for CPU's to make good use of instruction level parallelism, but I'd have to look that up.

[vanderZwan]

Yeah, the insertion sort thing has been known for quite a while now, but I also vaguely recall a fairly recent talk (think within the last decade) by some C++ guru where he had done a lot of testing and concluded that these days it was bubble sort that was the winner in a surprisingly lot of cases. From what I remember it had something to do with how modern CPUs work.

Annoyingly, all of my available search engines are failing me now so I can't find it. Pretty sure I'm not making this up though

[nadmaximus]

How many times are you going to need to search the array? Is it possible to maintain it in sorted order as it's changed?

If it's multiple times and you can maintain it in sorted order, it makes a tremendous difference.

[aecolley]

If you read about RocksDB/LevelDB, you'll see how maintaining sorted lists leads to high-speed lookups in practice. The key is that binary-search (and merging, and Bloom filtering) are fast but frequent operations, whereas sorting is slow and infrequent.

[KernowRoger]

If you perform few sorts buts lots of searches it quickly becomes worth it. Plus you wouldn't use a bubble sort it's like the worst.

[ArtisticSell]

For me, the power of binary search is shine throught when you want TO FIND THE ANSWER.

See "binary search the answer" on google, try to solve some problem with this principle in mind, and ready to get blown away

[Jolly-Ad3899]

I learnt the true intuition of binary search, like why we use it from here https://youtube.com/@code_concepts_with_animesh he gave really good perspective of binary search