Binary Search - A Different Perspective | Python Algorithms

Binary search implemented in Python.

In this video we try to understand and implement binary search in Python, also called bisection search, a fundamental yet simple to understand algorithm. Binary search is one of the first you may learn in computer science class, but no matter how well you know it, it never hurts to understand your foundational algorithms better.

*Erratum*: the parameter name at the end was supposed to be "hi" not "high".

SUPPORT ME ⭐
---------------------------------------------------

BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------

[Mutual_Information]

Can’t overestimate how important it is to know this for coding interviews.

[drishalballaney]

FINALLY the video I want! please do more of these kind videos related to algorithms, sorting etc

[Simon-fusd]

I'm so happy that I found this channel. I can watch something that is interesting and actually important for my studies

[haibai]

Thank you for actually going over monotonic functions, they're much more widely used than just binary search on an array alone.

[sjeff]

I'm preparing for a coding interview and think that this is a great explanation. It's a lot simpler than many of the implementations out there online and a lot more intuitive as well.

[Alister]

It's funny how instead of clicking 'like' once, I click it like 3 times now for these videos

[monkeecrap]

I appreciate the depth with which you covered this topic. It shows how to view the algorithm from a perspective other than just “memorize it”. Thank you!

Never thought the meaning of search could be ambiguous in binary search. I always thought of me searching for a number, it's interesting to think about that the search can be to where to place that number. Once again great video always to the point and very precise and clear.

[abdulmasaiev]

"But, the array being sorted, I claim is actually not the property we're using here" -> proceeds to use the property that the array is sorted with regards to (lambda a, b : (b < 7) < (a < 7)) as the comparator

I have to disagree. You're still using the fact that the array is sorted, just not in the "traditional" sort. And the fact that the array we're usually binary searching through is sorted "traditionally" isn't usually used to enable the insertion of 7 specifically, but any number at all. The "traditional" sorted property of an array implies the (lambda a, b : (b < n) < (a < n)) sort for any arbitrary n (with the obvious caveats for "arbitrary") which is the sort that we actually need, and so we can run it knowing nothing about the array. Here we don't have that. Sure, it'll work for anything bigger than 5 or smaller than 4, but for instance where should you put in 4.5? And so without this "traditional" sorted property, if you insist on using binary search in it then for an initially unknown array dealing with these unevennesses requires introducing extra checks which put the whole thing into O(n), which defeats the purpose of using a binary search at all in the first place.

[Maurycy]

I lead algorithmic masterclasses for high school youth and although I personally use a different implementation I must say - this video is very high quality! I am very impressed.
I was ALMOST convinced to start using this implementation, but you aren't getting me this time!

[Doodle]

What I love about this channel is that every video gives me at least one insight about the topic.

[davidhuang]

Man this is a great way of conceptualizing it and makes memorizing small implementation details so easy! Awesome content

[jhonsen]

I think i am bit Late to your Channel but its better late than never. Someone pointed me in Medium to your channel and he wrote that this vidio changed his way of think in Binary Search. I think he was right. Its really intuitive way of teaching.

[linear]

I appreciate videos like these a lot as I don’t have any formal education w/ computing so basics like this are rlly helpful

[unclesheo]

@mCoding around 3:12 you say "I think that far too often, binary search is taught solely as an algorithm that works on sorted arrays. But, the array being sorted ... is not actually the property that we're using here."

That's a pretty misleading statement. I think it does more harm than good, as you're confusing "the algorithm" with "the algorithm's behaviour on a specific input". Yes, strictly speaking, the property we're using is: "only the elements that we visit need to be sorted". But exactly which elements you visit depends on the input. In order for the algorithm to work for ALL inputs, the WHOLE array MUST be sorted. Try finding an 8 in your second, no longer sorted, array. You'll land on the 9 instead.

[memespdf]

These videos are great! The new mic is also very good

[radek]

Here is what I feel is even more intuitive, as it works with simple invariant. Set lo=-1 (one before array) and hi=n (one after array). Then I want to preserve this invariant: lo always looks at T and hi always looks at F. Because what I am looking at when doing bin search is neither the first F, nor the last T, but the gap. So i while (hi-lo>1) and look if mid is T, then lo=mid (because invariant) and if mid=F, then hi=mid. And when this algorithm end, it gives two pointers. one to the last T and one to the last F, hence giving the gap in between with full symetrical view.

After that i can I can thing of what I really need in current problem. Do I need the first F?, do I need the last T? Can the asfer be after/before array? All of these are questions, that I solve after I get my bin search pointers :-)

[rdwells]

Thank you for providing a video on binary search that is good enough to show my students. Extra points for pointing out the potential for integer overflow when using almost any other language.

It may be worth pointing out that, bisect_left() and bisect_left() are the same as the lower_bound() and upper_bound() algorithms in C++.

[geansantos]

THANK YOU VERY MUCH: I tested it by making an array with 10million numbers, it found the number faster and only with 25 iterations rather than the 10million the normal code would need.

[feerasse]

It's still difficult to wrap my head around genearting Binary Search, but this is the closest I have come to deeply understanding the concept. Thanks.