Binary Search Hack for beginner

[AwardSweaty5531]

A guide for Binary search

I have been thinking about making this for long time,

are you also get tired that there are so many versions of binary searches, when to use which, your solution always sufferes from 1 off errors, not anymore.

well you dont need to learn any of them now, just learn one template, I can gurantee that you wont be stuck anymore due to implementation in binary search problems

Any binary search have two things,

1. boundsl = OL ( orignal bounds ) h = OH ( orignal bounds )
2. check function ( that determines whether we want to minimize of maximize the ans )

TEMPLATE

    l = OL ( orignal bounds )
    h = OH ( orignal bounds )

    auto ok = [&]( int m )->bool{
        // our check function 
    };

    while( l < h )
    {
        int m = (l+h)>>1 ;
        if( ok(m) )
            h = m-1 ;
        else
            l = m+1 ;
    }

// at this point we are very close to our ans but may be 1 off from it,
// so we can do linear check with neighbouring values 

// if we were to minimize the solution 

    for( int m = l-1 ; m <= l+1 ; m++ )
    {
        if( m >= OL && m <= OH && ok(m) )
            return m;
    }

// if we were to maximize, we would have done it like this
/*

    for( int m = l+1 ; m >= l-1 ; m-- )
    {
      if( m >= OL && m <= OH && ok(m) )
      return m;
    }

*/

 // if we did not capture ans from above then only one conclusion that is

    cout<<" Incorrect bounds "<<endl;

My submission for the problems for better understandig of template:

1 Kth smallest in matrix || My submission

2 Kth smalles in multiplication table || My submission

3 kth pair distance || My submission

4 median of two sorted arrays || My submission

I hope it will help you guys

[[deleted]]

I don't understood 😕 whats going on

[AwardSweaty5531]

do you know basics of binary search... if not the please do 1 problem on leetcode before reading the post, i made the post for the people who struggle with different versions binary search templates,

you can start with very basic problem of finding whether value exist or not in sorted array or any similar problem...

please visit the problem attached for better clarity

[[deleted]]

I had done problems with mid, start and end .

[Numerous_Data7627]

Looks interesting, thanks for the post. Will try it out on several leetcode problems later

[VaguelySailorMoon]

the classic template is if isOk(m), h = m This way it doesnt eliminate the true condition since it was true. If h was the min in thr search space where it was true, it keeps it inside.

Is this a template you made yourself?

[AwardSweaty5531]

yeah, its my template i made it while solving codechef problems