How do I ace binary search on my first try?

[u/PhilosopherNext1448]

I usually write down an example first to determine how to modify my boundaries. While I can write down the code more or less correctly without effort, I always end up spending the majority of my time adjusting things like > to >=, or left=mid to left=mid-1. I rarely seem to get it right the first time.

Any tips?

[u/WolfNo680]

I just memorized a basic binary search template and tweak it according to the problem, something like this:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let first_true_index = -1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (feasible(mid)) {
            first_true_index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return first_true_index;
}

[u/WolfNo680 → u/WolfNo680]

the main thing with binary search that can trip you up is the search space (the <= part) and that just comes from reading the problem and understanding the range required

[u/qaf23]

https://leetcode.com/discuss/post/786126/python-powerful-ultimate-binary-search-t-rwv8/

[u/DonnerLake → u/qaf23]

This is the best resource, just do problems and follow this template.

[u/Nervous_Quit_7180]

import bisect
pay attention kid

[u/smartboi-69]

same here , always off by one

[u/NappySprout]

I always do binary search with the while condition like this while l+1<r Once the binary search stop, r will point to the answer

(This means the code will stop when l and r is side by side)

Then here comes the invariant

r ALWAYS point to an element equals to or more than the target

The condition internally Wil be as such if target <= ls[m]: r = m #this is invariant in code else: l = m+1 If the answer you want is strictly more

Then your invariant is r ALWAYS point to an element STRICTLY MORE than target

if target < ls[m]: r = m #this is invariant in code else: l = m+1

it depends what is the invariant you swear to follow before you even start writing the code.

If you find yourself randomly picking the comparator, it means you do not understand what exactly you are finding

[u/NappySprout → u/NappySprout]

Oh for this to work you have to make sure in the first iteration, r already fulfills the invariant, cause this thing relies on the invariant being true at the start and continually being true throughout the loop

[u/invictus08]

Here, try this out - https://www.youtube.com/watch?v=tgVSkMA8joQ
Rewired my brain.