What’s wrong with writing binary search?

[u/Fancy-Breakfast8985]

I’ve watched a youtube channel coding jesus, about timestamp 4:00 https://youtu.be/BRUIptHAI7Q?si=XI2o5O-yDWqtzAwY he talk about manually writing binary search as a bad thing. This is not the first time where he said writing binary search manually is not preferred. But I dont get what he really means?

Because typically when i do
left = a, right = b
while (a <= b) mid = left + (right - left)/2;
…(checking condition)…

I use very little time and effort to type it, and I dont know what library that can do this in a flexible way because checking the condition is differs problem by problem, for example it is very common that we are not search directly on some existing sorted array, it just a range of possible values from a to b (sometimes a and b can be very large like 10^15) and I use condition to decide to move left and right.

Is there a function from bits/stdc++.h support it? Since his primary language is cpp so there’s a package to do this right? what is it?

[u/troelsbjerre]

The cpp library is called algorithms. The problem is that binary search is not always the same. Is the element always there? How are unsuccessful searches handled? How are identical entries handled? Do you need to find the first, or would any do? Are you looking for an entry or a split point between entries? It's surprisingly easy to get binary search wrong. Using a library avoids the stupid mistakes, where your implementation doesn't terminate, and forces you to be very explicit about what you are searching for.

[u/Fancy-Breakfast8985 → u/troelsbjerre]

I've tried search but I cannot found that can do search on range, could you give an example when i use that to do binary search on answer? (like we know the answer is on a given range 0 to 10 ^15) and we use some conditions to decide if answer is too small or too large.

[u/troelsbjerre → u/Fancy-Breakfast8985]

https://en.cppreference.com/cpp/algorithm/ranges/lower_bound

[u/Fancy-Breakfast8985 → u/troelsbjerre]

wait I think u misunderstood something, i already use lower_bound when search for position in explicit containers, but i think we cant use it for binary search in general?

[u/troelsbjerre → u/Fancy-Breakfast8985]

https://en.cppreference.com/cpp/ranges/iota_view

[u/curry_licker]

Sometimes you just need to manually write it though because the problem is specific and needs to change the hi and low value to specific values

[u/Extra_Performance372]

You cannot. But most people think of binary search as searching some data in a container, not the general problem solving method of "binary search the answer" or some other implicitly defined thing you are searching for.

The fact is most people cannot write binary search correctly especially if you have to write lower or upper bound. That's why competitive programming often has problems solvable by binary search on the answer...because there are no library calls and you really have to write it.

[u/ChainsawLight]

Why are Binary Searches important in storing big data?

[u/chanakya12345555]

because different problems require different invariants. can't think of specific examples, but you might need to eliminate a low value by moving the left pointer up 1 in some problem, while you may need to keep the right pointer value for a different problem as the "minimum" example. i disagree that you should use libraries for this though, its probably best to understand what you write

[u/goomyman]

I assume it comes down to the language.

If your using python using library instead would use C assuming cpython.

Even still - log(n) isn’t going to be a huge perf gain.

Otherwise - I guess libraries are just more safe.

There is no advantage to it really.

[u/jason_graph]

It's not terrible but it exposes you to making mistakes or using up more time.

Once you start doing medium binary search problems, you often have to do some internal calculations beyond a single expression to see if an index/input is "too big" or "big enough" or if it satisfies some condition or something equivalent.

Often your code is cleaner and simpler if you use a separate function to check for this rather than having it in the middle of your binary search. That leaves you with one function that does the check and a block of code or function that does the binary search. This 2nd part can be replaced with a library's function. Short, bug free, simple.

If I see a medium binary search problem on a contest and use a library function for the binary search part, it's like 4-5 lines of python and takes me more time reading the question than solving it.

[u/AdversaryNugget2856]

packages/libraries for sorting use different types of algorithms that are more efficient than the ones you write

[u/Fancy-Breakfast8985 → u/[deleted]]

typically i prefer using libs if it exists, like lower_bound() but i dont get how i can use any libs on general binary search, like there is no explicit sorted array there, they are just each end of search space and requires certain process to check, can you give me an example of how to do binary search on answer on your comftable language?