Binary Search tutorial (C++ and Python)

This is the most comprehensive lecture on the binary search. Find the target value, or the first value satisfying some condition, or approximate sqrt(x) up to some precision. Watch this lecture if you practice for competitive programming or for coding interviews. See the pinned comment for links and my implementation. Consider turning captions on and setting the speed to x1.25.

Please give me suggestions about the format of a lecture or about topics for future lectures.

I’m Kamil Dębowski, better known as Errichto. I compete in and organize programming competitions. I make educational streams on Youtube and Twitch. I'm a finalist of ACM-ICPC, Topcoder Open, Facebook Hacker Cup and Google Code Jam. I got a second place in Google Code Jam 2018. I am/was nutella in Codeforces and target in Topcoder.

Watch me if you want to practice for coding interviews, competitive programming or just algorithms in general. I share my thought process, explain everything, and mention similar problems and techniques/algorithms.

[Errichto]

Note that some problems aren't same with what I talked about during a lecture. For example, Find Peak Element in Leetcode seems harder because the function can have multiple peaks.

Huge thanks to Reddy for making captions!

[kshitijpatil]

The most important lesson I learned from this video, don't bother updating low/high conditionally, stick with only one binary search template (for 99% of the cases), and use a variable instead to store pivot position as per your condition. It makes every binary problem 10x easier for me.

[naughtyrishan]

Thanks so much for such videos. A lot of people struggle badly to be good at competitive programming. You make their life easy. Thanks again.

[sarveshdubey]

Hi, Sarvesh from India
Please keep making such Conceptual videos.

[sauravpaul]

Best lecture on binary search implementation, thanks Errichto.

[rajbapat]

Great video! I can finally write binary search without hesitating or wasting time debugging a +1/-1 issue.

[medievalogic]

I finally understood the idea of "getting a better answer". Most binary implementation on the Internet look like hacky, with people incrementing or decrementing the mid by one to get a desired answer. Thanks a bunch.

[dharmanshah]

Thanks errichto for the well prepared material and thanks Reddy for captions!!

[TheGanesamurthi]

The best half hour that I spent in entire 2020

[SumitBadsara]

This is the actual binary search! Not just (L+R)/2 . Thanks for these examples. Keep making such videos. Love from India🇮🇳.

[AniketKumar-xgky]

It is so far the best binary search video I have watched on YouTube, Thank You very much....

[rajansaharaju]

It's really safe zone but didn't think before. Thanks. L + (R-L)/2 = (2L + R - L) /2 = (L + R)/2

[dcodernz]

Thanks Errichto! This was by far the best explanation I've seen/heard of binary search! I thought I had understood it before but this has deepened my understanding profoundly. The length is also good. I think it would help us all a lot of you did more videos like this to really get a deep understanding of algorithms.

[shubhamagrawal]

Thanks Errichto, after watching this video now I have a better understanding of binary search and its applications.

[shroud]

World class video must watch everyone👍

[nijikatherock]

that observation where we can generalize the problem to a prefix of Falses and a suffix of Trues was mindblowing. thank you so much!

[anands]

Usually really smart people like u are not known for their great teaching skills...
U really changed that!

[franceshe]

Thank you! This is one of the best algorithm video with clarity and great explanations I saw so far! I learned so much, plz keep update these algorithm videos, maybe the more general ones that people used everyday. I think that might have a bigger impact for the general public :)

[prabhatsharma]

You cannot find a lecture on binary search better than this!

[rohanarora]

All the things I learnt over weeks in a small 30 min video, thanks errichto!