Binary Search tutorial (C++ and Python)

[@Errichto]

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!

[@earth20010]

Thanks!

[@swagatochatterjee7104]

I was trying to apply that ans = mid template for finding the minimum element in a sorted array. Was I doing something wrong?

[@jdhp3696]

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.

[@Sehyo]

4:20 Since (L+R)/2 would overflow, shouldn't (L/2) + (R/2) work though?

[@roufshaik3530]

what would be the eps value in sqrt() function?

[@kshitijpatil2019]

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.

[@maximus1172]

Very insightful I must say

[@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.

[@musicfan1695]

adding to that, you are a very humble person as well.

[@sarveshdubey9347]

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

[@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.

[@rajbapat5607]

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

[@sauravpaul4131]

Best lecture on binary search implementation, thanks Errichto.

[@AnkitJosh]

Period

[@mujtabahussain7015]

@@AnkitJosh .

[@joshiakhil007]

@@AnkitJosh comment

[@TheGanesamurthi]

The best half hour that I spent in entire 2020

[@dharmanshah1239]

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

[@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!

[@AniketKumar-xg3ky]

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

[@shubhamagrawal2407]

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

[@rohan8arora]

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

[@Nyquiiist]

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!!!

[@SumitBadsara]

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

[@devendrasingh4776]

Well it is correct but will give int overflow . So it better to be on safer side . Thats it .

[@SumitBadsara]

@@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.

[@devendrasingh4776]

@@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.. 😊

[@prabhatsharma284]

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

[@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.

[@franceshe1350]

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 :)

[@srikanthkoraveni8210]

Thank you very much. Please continue to make videos covering the fundamentals. Loved the clear, concise and comprehensive presentation.

[@shroud3354]

World class video must watch everyone👍

[@dominikdabrowski7082]

I was really struggling with binary search, but your video made all the difference, thanks Kamil!

[@de_naenae]

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!

[@codepractices7]

Thank you so much errichto! Please continue to make such comprehensive tutorials!!

[@anweshbhattacharya8017]

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!

[@Woef718]

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!

[@kaushaldawra3527]

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

[@codexhammered007]

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

[@pradyundevarakonda6849]

This channel is a goldmine! Glad I found this before getting my cs major

[@BGivo]

That was great, thank you. More videos like this, where you introduce a concept, and then provide related examples, would be amazing.

[@gupta_samarth]

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.

[@iamtrash288]

Thank you for the comprehensive explanation of binary search! I really didn't know it was so powerful before!

[@adityarai8963]

This is by far the best video for binary search. Kudos to your amazing work, Errichto!

[@shroudyboi5673]

Wow he has explained the concept of discrete binary search beautifully. The topcoder tutorial was good but this video covers the topic really well

[@darshantawte7435]

Best video on binary search I have seen till now

[@sameerbhatti363]

Great video! You helped better understand binary search, but more importantly, its implications. You are a great teacher. Thank you.

[@anands9407]

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

[@kpopisthebestful]

You should do more of these lectures, like sorting algos and data structures

[@nayanchudasama2014]

What a great lecture, now binary search is Perfectly clear. Thanks a lot sir

[@rahulsbhatt]

This is legit the best binary search video anyone has made 👏

[@rajansaharaju1427]

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

[@GreatKrish1]

I think 2L and L+R will overflow

[@zafirhasananogh2421]

@@GreatKrish1 they were probably demonstrating how L + (R-L)/2 and (L + R)/2 is the same but does not overflow

[@lovleshbhatt7797]

need second part of this lecture as soon as possible , its a humble request from the fan side

[@psibarpsi]

This was great. Helped me learn a lot. I would be looking forward to more such sessions.

[@raselhasan2433]

I loved your lecture, as a teacher/trainer of coding, you are best. Thanks man.

[@himanshulal4454]

Excellent way to cover Binary Search using a systematic way.. Thanks a lot

[@matiyasyohannes5502]

This is the best lecture on binary search. Thank you Errichto

[@amritbhardwaj99]

This is a MUST watch vid on binary search!!

[@wizardOfRobots]

Thanks for the great lecture! Instead of a template, you gave me a proper way to think of the algorithm.

[@lpdc9767]

Thanks so much for the clear and concise material! I hope you keep making these.

[@Rich65501]

Excellent -- thanks for the correct way to calculate the midpoint in binary search.

[@doejohn5637]

what a brilliant idea of thinking binary search problems as elements of search space being T or F !

[@jannoszczyk5132]

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!

[@priyanandshukla8388]

One of the best lectures on binary search

[@namanbudhiraja6756]

Hey Errichto, after watching this video , i have solved my all doubts related to binary search.Thanks for the amazing explanation.Love from India

[@rehanakhter4813]

Best explaination of binary search in youtube. Thanks a lot!

[@literallynoone2093]

Thanks a lot man! I was struggling to get a hold of all the variations. You made it so simple!

[@sanddevelopers]

Thanks a lot for the clear explanation

[@alexneagu4466]

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.)

[@kairatopa9564]

Thanks man u made my interview preparation much easier

[@chandup832]

I have lost from rotated array, till then it was awesome!

[@yawningcats]

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

[@KarthikKarthik-el5hh]

thank you so much errichto, ur explanation was awesome now i understand binary search better

[@133839297]

Let's keep it binary with 2 words: PURE GOLD!

[@saitama-fv6my]

I watched your video and I got explained my topic what I wanted for. thank you so much sir 🙏

[@davidjiang7929]

Thanks for sharing! Your explanations are clear and concise. Also congrats on recent win!

[@icenberg5908]

Thanks errichto for your efforts and clear presentation.

[@blu5037]

Wow, super great video. Thanks for making this errichto.

[@mehedihasanjoy8726]

Pls do a leture on basic greedy and DP

[@Errichto]

I'm planning a lecture on dp, actually. It should be out soon.

[@abhishekdhok5245]

CP God for a reason.. Love your efforts. Love from India

[@pradiptarakshit35]

Please, do a lecture on Graph Algorithms. Also, thanks for this video.

[@geekySRM]

This is so awesome! Thank you so much @Errichto!

[@becomingbesthackerprogramm4644]

Lovely classic lecture , mesmerized by explanations , thanks alot ❤️

[@Sean-jv6bd]

Hi Errichto this is an amazing lecture! Thank you so much and please keep up the great work!

[@yilinma8367]

I wish I watched this video earlier. The True & False pattern is so helpful!!!

[@SushantKumar-iy4is]

Well explained, Errichto. Clean and Simple.

[@cccctainvista]

Great video, love it, you are very good at making complex problems seem very simple!

[@thuanvo9283]

Your ways so easy to understand. thank you Eric so much!!!

[@omti]

Very cool content! Thank you! Waiting for more videos...

[@abhishekgaurgaur]

Thank you very much Errichto, really appreciate it. ❤️

[@SuperArjun11]

This was great. Will you be covering data structures/algorithms not typically found in undergrad books? Square root decomposition and seg trees for example.

[@ajr1791ze]

yes, i also say so.

[@Errichto]

Yes, I plan both sqrt deco and seg trees :) More video ideas here: github.com/Errichto/youtube/wiki/Video-ideas

[@kushagrasahni9708]

@@Errichto Please make a video on segment and fenwick trees.

[@koocheukkeijacky9704]

Really appreciate of your videos !! very clear explanation

[@Errichto]

Thank you!

[@ivanleon6164]

greetings from Mexico! those videos are really cool, thanks for all the effort put on those.

[@adityakajale4403]

Best lecture on binary search

[@darshpatel8385]

This video was really helpful to me. Thanks for making such good content.

[@rohanvtk]

2:46 the correct formula and the reason why :)

[@areebwadood6273]

Great learned some new applications of binary search

[@barakode414]

Thank you very much. It's easy after watching your video.

[@abdurrahaman388]

Most informative binary search tutorial ❤️

[@laskdkmgful]

Best lecturer I have seen. Thanks!

[@__-to3hq]

"The study from 1988 showed that only one in four textbooks has a correct implementation..."

[@beanlighter9491]

Thank you so much sir. Countering problems with that T...F was quite interesting I will try sometimes

[@primerevan8403]

Just clicked before thinking let's watch something might come up .

[@murahat98]

Everyone else: Use (l+r)/2 to find the middle element. No problem at all. Errichto: Never use this formula xD

[@avisekshaw4748]

Great work bro. Thank you for uploading such a great content.

[@bharat_india12]

In this video first find the range which satisfy which is true and not satisfied which is false and applied binary search in the range to find last true or first true of first false or last false . Other case in which only one point is answer use mid and check goes to left or right or current mid is answr to return.

[@teezp12490a]

Thanks for the video! Came here from Joma's vid

[@rajgarg8883]

Thanks, Please make videos on educational round problems.

[@omanshsharma6796]

thanks a lot enrichto!! beautifully explained!!

[@aabhassaxena2490]

The overflow you talked about in the java library Will have no affect in competitive coding bcoz there the constraints are small so we will not have array of such big size and therefore overflow will never occur

[@Errichto]

1) We will eventually work with arrays of size 2e9. It might already happen in unusual contests like Distributed Code Jam. 2) The array is not always given explicitly - examples are computing floor(sqrt(x)) or interactive problems. It's better to use binary search that will always work.

[@yamisekai]

Thank you for sharing your knowledge, great video!

[@ajr1791ze]

amazing lecture. Thanks !