Binary Search - A Different Perspective | Python Algorithms

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.

Very, very useful. Thank you.

Fantastic

I am v confused while writing Binary search algorithms. I keep messing up whether to return left, right or mid, whether to use left <= right or just left < right and the edge cases. The approach mentioned here seems to not work for problems such as 33. Search in Rotated Sorted Array. Could you mention an intuitive approach to not get confused about the above things?

bisect

Por que el while lo <= hi: hi = mid + 1 no es correcto? También hay while hi - lo > 1: lo = mid, hi = mid

설명이 진짜 좋아. 고맙다^^

Meguru-style binary search is the most bug-free implementation.

2 words for you, my friend...
Thank you!

Thankyou for this brilliant way of explaination and you also helped to look a problem with altogether new angle

This is so helpful! I like your reasoning. Everything is well justified.

Wow

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.

this is brilliant

thank you

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.

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.

Thank you very much!

thankyou so much for this great explanation

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

And what if the array doesn’t have to be an integer?

Great video!

I'm sure this is good info but without walking through the algo with a few examples, I find it very hard to follow along.

This helped me make an algorithm to solve a similar problem!
Thanks, James.

Wait im confused when he said False value and True value shouldnt it be the reverse

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.

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?

Left bisect concept is used to find Minimum time,Minimum Height questions using binary search.

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.

Extra points for type hinting.

Wait what?? Python can handle arbitrary large integers?? How does that work exactly? I've never heard that before... I looked on Google but could not find an explanation of how that works. I just found things like "it is possible to handle larger values as memory is available" but that's not much of an explanation...

ru nick white's brother

Great explanation!

I have watched several of your vids and I have to say I’m a fan you make python sexy.

Great I cant believe the number of times I have seen people make this error occur all because they wanted to play doctor for shame.

Mid = low + (int) ({high - low}/2) much better approach for mid,

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

In Python, binary search is easy. Don't get me started on the numerous single-linked lists in C programs. They cannot be easily indexed and code containing them is riddled with linear search algorithms.

how about an video on "stupid ways to do something in python"

I’m too queer to not keep hearing bisection search as bisexual search

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.

Here's an implementation closer to what I use:
...
while lo + 1 < hi:
mid = (lo + hi) // 2
if arr[mid] < x:
lo = mid
else:
hi = mid
return hi
I know the implementation in the video is faster because it only uses addition when arr[mid] < x

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 ?

Great sir, I have a doubt, sometimes we return l, h or store our ans, Sometimes l<h or l<=h , TBH it is pretty confusing, could you please tell how to deal with this issue?
Thanks.

"slap like button odd number of times" very precise

this dude FUCKS