Binary Search - Leetcode 704 - Python

0:00 - Read the problem
0:58 - Drawing Explanation
5:10 - Coding Explanation

leetcode 704

#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[tanmay______]

Thanks for mentioning the integer overflow problem!

[jameelshehadeh]

It's fascinating how beginner friendly this explanation was despite how professional you are, thank you

[numberonep]

Always good to practice the basics! I am just happy to recieve a notification from neetcode :d

[h.t.]

can't thank you enough for ur tutorials! it's for sure in depth and easy to digest!

[bartekbinda]

I’ve actually always coded the binary search using the distance approach and never thought about your original approach to determine the mid point, thanks

[JamieDawsonCodes]

Great video! It helped me with this!
For those coding in JavaScript, be sure to make the middle variable: let middle = Math.round((left + right) / 2); Otherwise the value will be 2.5 instead of 3.

[Ashley-mcbi]

My data structures professor secretly gets his entire lectures from your videos! Except you explain things much better lol. Thanks for all your help!

[hamedbavar]

the recursive approach.
if len(nums) == 0:
return -1
mid = (len(nums)) // 2

if nums[mid] == target:
return mid
elif nums[mid] > target:
return self.search(nums[:mid], target)
else:
result = self.search(nums[mid+1:], target)
startIdx = mid + 1
if result != -1:
return startIdx + result
else:
return -1

[staffeng]

There's also a version of binary search where we would need to return where the element's index would be had it been there in the collection. And this is exactly how Collections.binarySearch() and Arrays.binarySearch() is implemented in Java. For example, you have a collection [1, 2, 3, 4, 5] and if you search for 0, then Collections.binarySearch() will return -1 but that's because 0 would have been at the first place at index 0 so it's that index 0 in negative form minus 1 which is equal to -1. To take another example, let's say you are searching the same collection for element 6, then Collections.binarySearch() will return -6 (-5 - 1).

[re]

The best explain to beginner including the integer overflow I ever seen

[hyungminkim]

Hi,
Is there a pattern or a rule when choosing whether l <= r or l < r when we are using two-pointers and while loop?
I have been watching your vids for a while and there were different situations when you used l < r or l <= r.
I was just wondering if it depends on the situation or if there is just a pattern for using either one.

[SENSEIFILES]

that log n breakdown just helped me for sure !

[abhimanyuambastha]

I've always implemented the binary search using the distance method. I guess thats how they teach in all good algorithms course. But never knew the reason why

[HibiTeamQueso]

Lol it's so hilarious that the last way you showed it's the one I did.
Cause I was like surely it has to be simpler but I guess not 😂

Took me a few tries to come up with it

[doodle_mo_ka]

but you also have to add something for that solution of overflow problem, Because when the array have only one element, right would be negative in te while loop, they've been tricky these days

[chessingh]

Ah, neetcode doing the daily leetcode challenge 🥺🏆

[dkijc]

Thank you for the video! Is there a way to do this with recursion??? Thanks!

[dewangpatil]

Hello Sir i am a big have a very important Could you please make solution playlist of Striver's SDE Sheet. Its will be very beneficial for us students

[jasonnguyen]

Thank you, your explanation is amazing

[chai]

Thanks for the video! I think it helps to mention the // syntax is a floor division, I have been implementing unnecessary checks on whether the array length is odd or even🥲