Binary Search - A Different Perspective | Python Algorithms
ฝัง
- เผยแพร่เมื่อ 19 เม.ย. 2021
- 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".
― mCoding with James Murphy (mcoding.io)
Source code: github.com/mCodingLLC/VideosS...
Longest Increasing Subsequence, uses bisect_left (20+ mins, old mic) video: • Longest Increasing Sub...
SUPPORT ME ⭐
---------------------------------------------------
Patreon: / mcoding
Paypal: www.paypal.com/donate/?hosted...
Other donations: mcoding.io/donate
BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------
Discord: / discord
Github: github.com/mCodingLLC/
Reddit: / mcoding
Facebook: / james.mcoding - วิทยาศาสตร์และเทคโนโลยี
![[UNCUT] ฝันรักห้วงนิทรา | EP.8 (4/4)](http://i.ytimg.com/vi/RDYJYiDwsj0/mqdefault.jpg)
Can’t overestimate how important it is to know this for coding interviews.
Being able to explain is sometimes just as important as being able to write it!
give an example please?
@@khappekhappe133 Find the 'pivot position' of a rotated sorted array. That one jumps to mind.
can’t overestimate* 😁
sorry for the pedantry but I agree with your point
@@mohammedj2941 gah! thank you - corrected!
FINALLY the video I want! please do more of these kind videos related to algorithms, sorting etc
Sure thing!
+1 to this
I'm so happy that I found this channel. I can watch something that is interesting and actually important for my studies
Welcome aboard!
Exactly. There is no bullshit or drama here either. Just fun in coding itself. Wonder why he doesn’t get more subscribers.
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.
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!
Glad you enjoyed it!
Thank you for actually going over monotonic functions, they're much more widely used than just binary search on an array alone.
I always think about it as std::partition_point from C++
It's funny how instead of clicking 'like' once, I click it like 3 times now for these videos
A true fan!
i slap it four t
y one times :P
@@mCoding you mean True*
@@NaifAlqahtani true, false = True, False
What I love about this channel is that every video gives me at least one insight about the topic.
Thanks so much!
Thanks a lot, James! Your explanations are awesome. One of the best Python related channels on TH-cam. Subscribed with pleasure.
Thank you so much for the kind words!
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.
Thank you!
this was a crystal clear presentation and thanks for step by step writing the code. please do more videos like these!
Sure thing!
These videos are great! The new mic is also very good
Yay, thank you!
Great vid! Knowing when to use slice indices vs element indices is important for many problems involving arrays
Glad it was helpful!
I'm currently learning about binary search and and other searching algorithms and this video definitely helped, thanks a lot
Great to hear!
Love that you are improving your recording. This is much easier to read. =]
Yay, thank you!
This helped me make an algorithm to solve a similar problem!
Thanks, James.
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.
This is so helpful! I like your reasoning. Everything is well justified.
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.
Thankyou for this brilliant way of explaination and you also helped to look a problem with altogether new angle
And thank you for your kind words!
i found this right after successfully implementing basically that exact strategy at 4:40 to find the location of a cell in a 2d array. it is really really satisfying to implement even a simple search like this
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!
Thanks for sharing! Maybe next time!
I suppose different algorithm keeps lo at true value and hi at false value.
Also it didn't use an increment of mid index.
And finally different loop condition stops exactly at lo=1+hi.
P.S.
lo initialized by -1 😉
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++.
Thank you for sharing my video with your students, and the cpp algos were indeed the inspiration for this video!
Love the videos James, very good explanations.
Glad you like them!
I was just studying this morning! Great video!!
Awesome! Thank you!
I can see from the level of articulation that you must have some mathematical background. You covered well all of the ifs and buts one raises when writing any algorithm, and actually gave a rigid proof for the validity of the presented bisection method! Hopefully this video will be used as "the" tutorial on bisection search in the future.
You are correct, I am a trained mathematician! Thanks, I hope so!!
Great video as usual 👍 I’d be really interested to see you go through a merge sort algorithm because I find them very hard to understand logically. I understand that you split the components up and reorder them in increasingly larger groups, but I don’t understand where the efficiency of it comes from because it seems like there are still a lot of steps.
Maybe that’s just me though! Anyhow, if you DO do some more videos on sorting algorithms I’d be really interested to hear your explanation of a merge sort, you have a good way of explaining things.
Probably will!
설명이 진짜 좋아. 고맙다^^
THANK YOU VERY MUCH: I tested it by making an array with 10million numbers, it found the number wayyyyy faster and only with 25 iterations rather than the 10million the normal code would need.
I appreciate videos like these a lot as I don’t have any formal education w/ computing so basics like this are rlly helpful
You are welcome!
Very, very useful. Thank you.
thankyou so much for this great explanation
Great video!
Great explanation!
7:45 to change your code to implement bisect_right() instead, replace lines 6-10 with the following:
if arr[mid] > x:
hi = mid
else:
lo = mid + 1
return hi
this is pretty much the same thing as changing the if condition to
if arr[mid]
Thank you so much for the explanation. By my understanding, lo will be the first index that the condition is false, and hi will be the last index that the condition is false. So when the condition is true, we can directly update lo = mid + 1, because like you said, that might be the first index in which the condition is false. We don't update hi = mid - 1, because, when we update hi = mid - 1, There might be a case that mid is the first F, so we might miss that F, therefore the best we can do is update hi = mid.
My brain understand it better when i think of the if condition as
x > arr[mid], idk why but thank you for this vid
This is a crystal clear explanation!. thanks a lot. I can't help subscribe this channel haha
Welcome!
Please make more videos on Algorithms and Data Structures!!!
Thanks for this video❤️
Sure thing! These take a loooot longer to make than the other videos though :( Glad you liked it!
Thank you very much!
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 :-)
This is awesome, thank you for making this video..
My pleasure!
Fantastic content as always
Much appreciated!
this is brilliant
Very useful, thanks!
Glad to hear that!
Excellent Video!
Thank you very much!
I recently used binomial search for finding the cutoff value that minimizes the distance between specificity and sensitivity of a model. The brute force method, that calculated the values at 100k different points, took about a minute to run, binsearch needs 3 seconds
I recently did something similar with binary search for the altitude where the 3D surface area above and below that altitude are a specific ratio. It becomes a powerful algorithm when you realize it can search any "sorted" space, discrete or continuous, instead of just arrays.
@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.
If you knew that you were always going to search for 0, say, then you would not need the array to be sorted. The sorting requirement comes only from the fact that you do not have any extra information about your input. The real precondition for bisect(arr, x) to work (this implementation at least) is not two separate conditions on arr and x, it's a joint condition that arr is partitioned wrt x. This is the property that is actually used in the algorithm and the property that helps you remember the implementation. Saying arr needs to be sorted is only a practical convenience to ensure that your array is partitioned wrt every element. The most common use case of course requires the array to be sorted. But if you really want to understand the algorithm and its true limitations, you need to drop that crutch. Bisection works in a much more general context than even 1D arrays, I may talk about its use in mathematics in the future, e.g. in random number generation or a proof of the intermediate value property of continuous functions on intervals.
@@mCoding Thanks for the answer, although I'm even more confused now.
If I knew I was always going to search for 0, why would I search an array of numbers rather than keeping track of the count of zeros?
If the array was the result of some other computation, which only guarantees it's partitioned wrt 0, then yes I could binary search for 0. But why should I? That other computation certainly knows where and how many zeros there are, right?
I see your point but hypothetically is a sorted array really a sorted array if you are if you are going to continuously try to add elements to it that are yet to find their order in the chain. He is assuming that the element is already there in an implicit way even though its not. Or rather tries to find its location based on a new perspective which only depends on a sorted portion. Not the whole. Here is how i imagineds it. Imagine you have an array of infinite numbers and the target you have "should" take place at the "end" yet the array is infinite how do i know the rest is hypothetically sorted? This approach solves that by ignoring whatever after the firsr occurrence of the target since we are going to reduce the hi pointer anyway to it to at most fit the size - 1 of the array tangibly.
"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.
Yes the fact that you can use binary search as a general searching algorithm will ever only apply to a sorted list. This indeed is just fact. Came here looking for someone else that realizes this.
@@t_kon ditto.
Yeah, I was super confused when he said that the array doesn't have to be sorted. Unless, of course, he was willing to increase complexity to O(n).
Also came to the comments to see if anyone else is seeing this now as O(n).
At 7:01 you add an assert statement. Worth noting that this is only executed when running in non optimized mode. A production ready implementation should rather raise a ValueError.
Thanks a lot for making this video
And thank you for watching!
Hey, how about discussing the square sum problem next? I find this one quite interesting.
Fantastic
I love you, great video
Thank you again for watching!
Left bisect concept is used to find Minimum time,Minimum Height questions using binary search.
for bisect_right implementation
(please keep doing more of these small quizzes/challs, i was watching the broadcasting video this past weekend and that one was fun to do)
``````
def bisect_right(arr: list, x, lo=0, hi=None) -> int:
hi = hi if hi is not None else len(arr)
if lo< 0:
raise ValueError(''lo can't be equal to the balance in your chequing account!')
while lo < hi:
mid = (lo + hi)//2
if x < arr[mid]:
hi = mid
else:
lo = mid + 1
return lo
Good! I hope you arrived here by first simply replacing < with
"slap like button odd number of times" very precise
I'd argue that the true/false property is still "sorting", just using a different sort function. Perhaps sorting by that function may perform better in some scenarios though? An interesting idea
It certainly can be though of as being sorted with respect to a different sort, technically, but this scenario usually goes by the name "partitioned" rather than "sorted".
new mic is awesome!
I think I'm getting the hang of it! It turns out I had a lot to learn about audio production, the mic was only half the problem!
great video!
Glad you enjoyed it
perfect :)
Thanks!
You can add the following lines after the loop to tell if value exists.
if lo == len(arr): return -1
if nums[lo] != x: return -1
I like to do it recursive and use it with a wrapper method. in Java for example:
public static int bin_search(int[] arr, int start, int end, int numToSearch)
{
int mid = (int)((start + end) / 2);
if(arr[mid] == numToSearch)
return mid;
return arr[mid] < numToSearch ? bin_search(arr, mid, end, numToSearch) :
bin_search(arr, start, mid, numToSearch);
}
2 words for you, my friend...
Thank you!
You are welcome!
thank you
great way to spend 4:20, thank you my bro
Took me too long to get this...
The abstraction is gold.
Thanks!
Great content.
PS: This guy doesn't blink
Huh... I never noticed! Should I purposefully add blinks in to make people feel better?
@@mCoding no! Just present in the most natural way you can. That blink thing was just an observation.
Hello,
Great lesson, thank you.
However, what I do not understand is:
hi = hi if hi is not None else len(arr) statement.
Looking at your bisect_left function I don't get where the hi value is supposed to come from if function doesn't take such argument. Do you have it assigned globally somewhere above? If not -> hi is referenced before the assignment here, isn't it ?
The function argument was supposed to be named hi as well, not high, sorry for this typo. The purpose of the statement is that if the user does not pass in a bound for hi, then the end of the array will work as an upper bound, otherwise use the bound the user passed in.
Extra points for type hinting.
Huh. When i tried writing a binary search i only kept track of the "middle" and tried moving that in the appropriate direction. It got too wonky to keep track of how big the next step should be and what to do with odd-number intervals, so i never got it to work. This makes a lot more sense.
nice!
Thank you! Cheers!
Meguru-style binary search is the most bug-free implementation.
Correct me if I'm wrong, but I think there is a typo on line 2 at around 7:00. It should be
hi = high if high is not None else len(arr)
Either that or changing the argument name "high" to "hi", although I'm not 100% sure this would work.
You are correct, thank you for pointing this out! The parameter name was supposed to be "hi" not "high"!
I went to go and fix it in the code but it was already fixed! I used the wrong take in editing!! Sorry for the mixup.
@@mCoding No problem. It was just a tiny mistake and overall the video was great! Keep on pumping out great content!
I was gonna write the same, plus: I believe you can simply write: hi = hi or len(arr)
@@PetrSzturc In this case you can't write hi = hi or len(arr) because what if someone passed hi=0? If you used hi = hi or len(arr), this would throw away the upper bound! I know it is inconvenient to use the longer None check, but it should be preferred in most cases because of tricky situations like this!
Would you mind sharing what colour scheme you're using in your editor?
Darcula, the default dark theme in pycharm.
If we use while lo
Hi professional noob here. I just found out the traditional binary search does not properly work for finding the first occurrence of element in a sorted list. Using the given example binary search insertion will do but will not guarantee the first index. We may or may not get the correct index. IT only ensures to INSERT an element at a position that maintains the sorted order. It is better to use linear search O(n).
We can extend the binary search by adding these steps: (Sort of a race condition solution in React)
1. Using a flag variable to store the mid where the condition list[mid] == x is true. -> This is for occurrence that is in the mid.
2. Adjusting the hi to (hi = mid ) to continue searching for the first occurrence in the left side. -> This ensures to find earlier occurrences.
3. Returning the flag variable that holds the last occurrence in the left side(first occurrence) at the end of recursion / loop getting the benefit of O(log n).
Binary search is use for sorted and unique list. Just sharing what I have learned for someone who is trying to find first occurrences and learning binary search to videos like this.
I am v confused while writing Binary search algorithms. I keep messing up whether to return left, right or mid, whether to use left
Yeah, I suppose it can't find edge values of the lists when I write low
banger vid
Thanks!
You should have been my professor 30 years ago
What is meant by "Overflow"? Why it is not while lo
Overflow refers to the result of a computation being too large (positive or negative large) to represent in the given data type. For example, if you are using 32 bit integers, x and y can be small enough to represent but x+y might overflow. So (x+y)/2 might not give you the average or of x and y even if x and y are small enough to fit in 32 bits because of overflow.
Checking if x == mid first could give you a shorter execution, but it could also give you a longer execution because it is now an extra step you have to do every iteration.
Thank you, now I have something to think about. Cheers@@mCoding
Wow
Does builtin bisects work with floats?
Yes! It works with any type that has a
Yes, this is technically a solution, but saying that "returning the position where you would insert the first one" is actually problematic in some situations and that's why you usually take formal classes to understand what to do when, not to mention you will most definitely find requirements for exceptions where no X is found. There is no magical implementation that solves everything. Also, there is a huge problem with the whole return the index where the first X would be inserted deal: say you want to find 7 in [8], you would get 0, sure, but does that mean there is a 7 or not? If you don't know the content of the list/array then that first element can be what ever and you would still get 0. It obscures a lot of information.
that's why there is an extra check at the end to compare whether the value at returned index matches the required value. This might be an extra step, but it removes a lot of complexities if you want to find first value, last value or find index where to insert which is very confusing if you go by normal binary search.
5:48 Can you please explain why fits false value couldn't be later than mid ?
In that case, the value at mid is a false value. The first false value cannot be later than mid because any later false value would be strictly after the one at mid and hence not the first one.
I remember struggling when I realized I wasn't sure how missing entries should be handled.
A common struggle!
So essentially, you differentiate between the search, and the returning of the index to deal with the exception.
This code is certainly valid for the implementation described, but if you gave someone a binary search function that was returning indexes in the middle of a list due to that being “where you would put it”, even if there’s no matching element, I feel like that would cause massive confusion, and you’ve thrown away a huge part of the semantics and use of binary search, just to save yourself having to handle the case where the searched value isn’t present?
If course we don't want to change the semantics from a yes no to an index for existing code, rather im suggesting to change your perspective of binary search from a yes no question to an insertion index question. Given the insertion index version, it is a 1-liner to create a wrapper that returns yes no, just check if the index is in bounds and has the element you are searching for. All outside code can then continue to use the yes no version, while you can maintain the easy to understand and remember implementation under the hood.
@@mCoding I guess that makes sense. What's the beneficial use case of knowing where you 'would' insert something but not inserting it?
Great sir, I have a doubt, sometimes we return l, h or store our ans, Sometimes l
Absolute wonderful video. I'm high as fuck and still understood everything very good
Check out my brownian motion zoom videos! th-cam.com/video/UT7AG2OoYZo/w-d-xo.html
At 6:56
Line 2 should be
hi = high if high is not None else len(arr)
See the erratum in the description!
@@mCoding oh that also fixes it
@@mCoding btw, Great video very informative
github repo for the code? :)
And what if the array doesn’t have to be an integer?
Por que el while lo 1: lo = mid, hi = mid
Please, I need to know what font that is.
JetBrains Mono, aka PyCharm's default font.
A problem that uses binary search the answer could be the next video to explain the usefulness of this algorithm.
I already made a video about a problem using it! th-cam.com/video/NIiYzjCNadI/w-d-xo.html It's a long one though.
@@mCoding Yeah LIS is a great one.
lo + hi = lohi (= salmon in Finnish)
Haha!
This guy is like the Nick White that isn't a poser
3:11-sorry, what? If the array is unsorted as [2, 3, 5, 4, 6, 9, 8, 7], then how would it find the 7?
The key property needed is that everything less than 7 is to the left, and everything bigger than 7 is to the right. Your array does not satisfy this constraint.
Ah, got it. You did say that. Thanks for engaging with me!
@@mCoding : So what you're saying isn't that it doesn't have to be sorted. What you'rs saying os that it just have to be sorted in a different way. A binary search will not work on a completely unsorted array, which is what you're claiming it will in the video
binary search can be written a little cleaner and simpler, without any + 1, and the algorithm, in my opinion, would be more understandable
You would run into an infinite loop if you didn't have the +1 here. Do you have an implementation that you could share?
@@mCoding Sure: ideone.com/6i4x35
In that implementation indexes of elements, that are lower than x for sure, less or equals left variable.
the only problem is that if x is greater tan every element in the list, this algorithm will return len(a) - 1.
It assumes that the last element is bigger or equals, we can check that in the beggining, I suppose
You would additionally need to check the list is not empty so you don't return -1 either. But I think you can make it work. It's also not clear exactly what the loop invariant is in this implementation or why the stop condition is >1 instead of >0 (I mean besides "because it makes it work"). These are the kind of details that I was hoping to not have to memorize. It's a worthwhile exercise, but I think I prefer it with the +1 to avoid all the corner cases.
how about an video on "stupid ways to do something in python"