Binary Search tutorial (C++ and Python)
ฝัง
- เผยแพร่เมื่อ 18 ม.ค. 2025
- 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.
Frequently Asked Questions: github.com/Err...
Github repository: github.com/Err...
Facebook: / errichto
Twitter: / errichto
Competitive Programming Discord: discordapp.com...
TH-cam channel 1: / errichto (mainly short videos)
TH-cam channel 2: / errichto2 (streams)
I’m Kamil Dębowski, better known as Errichto. I compete in and organize programming competitions. I make educational streams on TH-cam 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.
I recommend solving binary search problems on Leetcode (leetcode.com/explore/learn/card/binary-search/). Don't read their templates though, they aren't perfect.
Start with easy problems: leetcode.com/explore/learn/card/binary-search/125/template-i/951/, leetcode.com/explore/learn/card/binary-search/126/template-ii/947/, leetcode.com/explore/learn/card/binary-search/126/template-ii/949/.
You can find C++ and Python codes to some problems in my GitHub repo, github.com/Errichto/youtube/tree/master/lectures/binary-search.
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!
Thanks!
I was trying to apply that ans = mid template for finding the minimum element in a sorted array. Was I doing something wrong?
Thank you for the wonderful video. It really help me understand the algorithm better. It will be really great if you can do more videos like this where you go over other data structures and algorithms that are most used especially in interviews.
4:20 Since (L+R)/2 would overflow, shouldn't (L/2) + (R/2) work though?
what would be the eps value in sqrt() function?
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.
adding to that, you are a very humble person as well.
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.
Hi, Sarvesh from India
Please keep making such Conceptual videos.
Best lecture on binary search implementation, thanks Errichto.
Period
@@AnkitJosh .
@@AnkitJosh comment
Great video! I can finally write binary search without hesitating or wasting time debugging a +1/-1 issue.
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.
that observation where we can generalize the problem to a prefix of Falses and a suffix of Trues was mindblowing. thank you so much!
Thanks errichto for the well prepared material and thanks Reddy for captions!!
The best half hour that I spent in entire 2020
It is so far the best binary search video I have watched on TH-cam,Thank You very much....
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.
Thanks Errichto, after watching this video now I have a better understanding of binary search and its applications.
All the things I learnt over weeks in a small 30 min video, thanks errichto!
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 :)
Thank you very much. Please continue to make videos covering the fundamentals. Loved the clear, concise and comprehensive presentation.
Thank you so much errichto! Please continue to make such comprehensive tutorials!!
This is the actual binary search! Not just (L+R)/2 . Thanks for these examples. Keep making such videos. Love from India🇮🇳.
Well it is correct but will give int overflow . So it better to be on safer side . Thats it .
@@devendrasingh4776 Bruh! That was just an example 😂. I meant he is not teaching the concept. He is teaching practical implementation. Like after this, some people might see binary search with a totally different perspective.
@@SumitBadsara exactly . I am that guy who has changed perspective. Now i think like more of finding that condition rather than blindly dividing into half. All thanks to this guy.. 😊
Hands down the best explanation I've come across on BS yet. Looking at it from a a PoV of prefixes and suffixes was really eye opening, and has made solving some problems suuper easy. Thank you!!!
You cannot find a lecture on binary search better than this!
Thank you Errichto for the top-notch pedagogical content. Your techniques in this video helped me in one particular question in a technical interview for Amazon. I didn't receive the final offer, however it was a great experience thanks to you!
This channel is a goldmine!
Glad I found this before getting my cs major
That was great, thank you. More videos like this, where you introduce a concept, and then provide related examples, would be amazing.
I was really struggling with binary search, but your video made all the difference, thanks Kamil!
World class video must watch everyone👍
Really awesome lecture. Thanks a lot for all the time you put into preparing this stuff. All those hours of BPS surely do pay off. Can't wait to learn more things from you.
You should do more of these lectures, like sorting algos and data structures
Very intuitive explanations. I have never come across keeping an "ans" variable but it makes so much sense. Much easier to understand than other solutions!
This is by far the best video for binary search. Kudos to your amazing work, Errichto!
This is the best lecture on binary search. Thank you Errichto
Thank you for the comprehensive explanation of binary search! I really didn't know it was so powerful before!
Thanks a lot for the clear explanation
Best video on binary search I have seen till now
Congrats, Kamil, for a great video! With every video i learn more and more. Please make more videos like this, where you explain other popular algorithms. (segment trees, graph theory, string algoritms like KMP, etc.)
Właśnie znalazłem twój kanał po obejrzeniu twojego wywiadu z Joma.
Bardzo dokładnie i prosto wszystko tłumaczysz. Zdecydowanie najlepszy kanał z algorytmami jaki dotychczas widziałem!! Keep it up!
Thanks so much for the clear and concise material! I hope you keep making these.
I feel this is the best binary search visualisation and strategy explanation because one thing is correct, it is a simple algorithm but at the same time it is very easy to write a buggy code for it.
Thank you
This was great. Helped me learn a lot. I would be looking forward to more such sessions.
Thanks for sharing! Your explanations are clear and concise. Also congrats on recent win!
Great video! You helped better understand binary search, but more importantly, its implications. You are a great teacher. Thank you.
This was great. Will you be covering data structures/algorithms not typically found in undergrad books? Square root decomposition and seg trees for example.
yes, i also say so.
Yes, I plan both sqrt deco and seg trees :) More video ideas here: github.com/Errichto/youtube/wiki/Video-ideas
@@Errichto Please make a video on segment and fenwick trees.
Thanks a lot man! I was struggling to get a hold of all the variations. You made it so simple!
Best explaination of binary search in youtube. Thanks a lot!
This year I was studying mathematics on university Leiden and I dont know but my interest to learn mathematics declined so much just by attending school. A month ago I dropped out and found your videos and now I fell in love with competitive programming. Thank you so much!
Thanks man u made my interview preparation much easier
Excellent way to cover Binary Search using a systematic way.. Thanks a lot
One of the best lectures on binary search
Thanks errichto for your efforts and clear presentation.
What a great lecture, now binary search is Perfectly clear.
Thanks a lot sir
I loved your lecture, as a teacher/trainer of coding, you are best. Thanks man.
This is so awesome! Thank you so much @Errichto!
thank you so much errichto, ur explanation was awesome
now i understand binary search better
Pls do a leture on basic greedy and DP
I'm planning a lecture on dp, actually. It should be out soon.
Really appreciate of your videos !! very clear explanation
Thank you!
Thanks for the great lecture! Instead of a template, you gave me a proper way to think of the algorithm.
In the sorted rotated array variation. It's safe to say that assume false when element at mid is greater than "or equal to" the last element. Only greater than would fail for the case when the smallest number is repeated. Eg. 6, 7, 9, 9, 15, 19, 2, 2, 3
Hey Errichto, after watching this video , i have solved my all doubts related to binary search.Thanks for the amazing explanation.Love from India
Usually really smart people like u are not known for their great teaching skills...
U really changed that!
"The study from 1988 showed that only one in four textbooks has a correct implementation..."
Excellent -- thanks for the correct way to calculate the midpoint in binary search.
Wow, super great video. Thanks for making this errichto.
Wow he has explained the concept of discrete binary search beautifully. The topcoder tutorial was good but this video covers the topic really well
This is a MUST watch vid on binary search!!
This is legit the best binary search video anyone has made 👏
what a brilliant idea of thinking binary search problems as elements of search space being T or F !
Thank you very much Errichto, really appreciate it. ❤️
Hi Errichto this is an amazing lecture! Thank you so much and please keep up the great work!
Great video, love it, you are very good at making complex problems seem very simple!
CP God for a reason.. Love your efforts. Love from India
Your ways so easy to understand. thank you Eric so much!!!
it was very good, I thought I new binary search but after watching this video I found out much more. It was really helpful. Thank you
Great video! Which topics do you plan to do next ? and will you focus more on cp or interview preparation?
You can read my video ideas in my GitHub wiki: github.com/Errichto/youtube/wiki/Video-ideas
I want to mix cp and interview prep.
Lovely classic lecture , mesmerized by explanations , thanks alot ❤️
I watched your video and I got explained my topic what I wanted for. thank you so much sir 🙏
Well explained, Errichto. Clean and Simple.
thanks a lot enrichto!! beautifully explained!!
Great work bro. Thank you for uploading such a great content.
I have lost from rotated array, till then it was awesome!
This video was really helpful to me. Thanks for making such good content.
Please, do a lecture on Graph Algorithms. Also, thanks for this video.
need second part of this lecture as soon as possible , its a humble request from the fan side
greetings from Mexico! those videos are really cool, thanks for all the effort put on those.
Let's keep it binary with 2 words: PURE GOLD!
Most informative binary search tutorial ❤️
Covers a lot of important observation and pattern in binary search.
Very cool content! Thank you!
Waiting for more videos...
It's really safe zone but didn't think before. Thanks. L + (R-L)/2 = (2L + R - L) /2 = (L + R)/2
I think 2L and L+R will overflow
@@GreatKrish1 they were probably demonstrating how L + (R-L)/2 and (L + R)/2 is the same but does not overflow
@@zafirhasananogh2421 Yeah that's what I wrote
2:46 the correct formula and the reason why :)
Great learned some new applications of binary search
Thank you very much. It's easy after watching your video.
Best lecture on binary search
Best lecturer I have seen. Thanks!
Hi Errichto, Thanks for such an amazing video. Can you please guide on how you write such clean and simple code? I have seen your code and ecnerwala's code in CF contests and they seems very crisp, precise and to the point, generally less then 50 lines. How to improve our thinking and coding to write such neat and to the point code?
Thanks in advance :)
Just clicked before thinking let's watch something might come up .
Everyone else: Use (l+r)/2 to find the middle element. No problem at all.
Errichto: Never use this formula xD
Thank you for sharing your knowledge, great video!
Thank you so much for this, I have a question for you @Errichto, is this implementation the one that you still using nowadays?
Thank you very much! You are incredible!
this is good stuff, now I know why people call you god of cp... orz
Thanks man, awesome perspective