Binary Search - Leetcode 704 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: neetcode.io/problems/binary-s...
0:00 - Read the problem
0:58 - Drawing Explanation
5:10 - Coding Explanation
leetcode 704
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#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!

[@CST1992]

This kind of attention to detail is what separates great from just good.

[@jameelshehadeh9011]

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

[@h.t.4846]

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

[@numberonep5404]

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

[@dragonoid296]

gotta do the classics sometimes

[@re4388]

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

[@bartekbinda6978]

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.

[@TheQuinnB]

Thank You!

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

[@SENSEIFILES]

that log n breakdown just helped me for sure !

[@jasonnguyen128]

Thank you, your explanation is amazing

[@dkijc]

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

[@AndersonSilvaMMA]

OMG thank you very much for your channel!

[@a.rohimsama7222]

Thank you. love it!

[@Ashley-mc5bi]

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

[@abhimanyuambastha2595]

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

[@hyungminkim6664]

Hi, Is there a pattern or a rule when choosing whether l

[@orangethemeow]

I used l < r, but you have to check in the end when l == r, whether nums[l] or nums[r] == target l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] == target: return m elif nums[m] < target: l = m + 1 else: r = m - 1 return l if nums[l] == target else -1

[@kwakubiney5175]

I am guessing it depends on if you need to do something with the l=r condition, also for binary search, if the element has just one element, condition l

[@thiagot7706]

Thanks, neetcode.

[@hamedbavar566]

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

[@tanoybhowmick8715]

Thank you!

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

[@nur_6ek]

you are legend bro😄

[@doodle_mo_ka4336]

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

[@chai01724]

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🥲

[@ericdwkim]

this comment cleared that up for me, thanks!

[@zeki7540]

that was great!

[@chessingh]

Ah, neetcode doing the daily leetcode challenge 🥺🏆

[@free-palestine000]

Do you have any advice on how to remember the fundamentals on a topic while you're working on other topics? I'm struggling to retain details from trees while im working on strings problems for example

[@cc-to2jn]

i would recc u do them in pattern order rather than randomly. This will help u truly understand the pattern and retain it.

[@bbbo85]

Grokking the coding interview is the answer you are looking for

[@mindsetnuggets]

Review old solutions or topics you've done every other day.

[@scvkurt03]

Use Anki to make flash cards. It’ll drill you every day using Spaced Repetition.

[@shleebeez]

@@scvkurt03 how would the problems/solutions translate to cards?

[@sanooosai]

thank you sir

[@jesuyedavid9497]

can we make the variable names more explanatory?

[@dewangpatil4990]

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

[@raghavkcc3234]

How can the list be added in the program????

[@TheRailJunction]

TIL how we get log n complexity..

[@masternobody1896]

nice

[@indhumathi5846]

understood

[@pradeepjigalur]

Can you explain, why it should be l=mid+1 or r=mid-1 not l=mid or r=mid

[@VedantaNayak]

Since we know mid is not the target, it will be redundant to include it in the next window.

[@darKnight_-_]

running it with m=l+r//2 doesnt work anymore you have to use m=l+l-r//2 only, otherwise it gives a time limit exceeded error

[@eteran23]

(l+r)//2 works just fine. Mind the brackets. In your m=l+l-r//2 you're really doing m=2*l - r//2, which works here, but is probably not what you intended to do.

[@darKnight_-_]

m=l+(r-l)//2 sorry@@eteran23

[@shurale85]

Why we can't just make left or right equal to middle without increasing or decreasing mid value? I know that's more efficient but don't understand why search doesn't work without modifying mid value

[@juandager5220]

Left and right limit the section of nums where the possible solution is. And middle is the current index that you are comparing to the target. If middle is not the target, you need to adjust the new size by updating left OR right. Basically, discarding the upper or lower half. And then check again the new middle. The easiest real life example is how you search a dictionary. Grab a physical thesaurus and search for a word... That's binary search! Does that answer your question?

[@pauljones9150]

What confuses me is what happens in an array with a single value and the target is LESS than the value contained in the array. ie. Array = [1], Target = 0. Code Variable Theoretical Printout. L = 0, R=0, M=0 Target is less than value at M, so R=m-1 and M=-1 L=0 R=-1 M=-1 Target is STILL less than value at M, so R=M-1, so R=-2 and M=-1?? Value at M can never be reached, as M will never get smaller than -1???? Neetcode, bless me with your knowledge of edgecases

[@CoolerJ0k3r]

The while condition is L

[@ikthedarchowdhury8947]

@@CoolerJ0k3r What if the Target is inside the left or right pointer itself? [-1,0,3,5,9,12] target 5. I changed the target to 5 in the given test case, the solution works fine, but how? Which line is handling that?

[@juandager5220]

You are confusing values with index. Target is the actual number you are looking for. Middle is the current index of what you are searching for. So when M=0, you are checking for the value of the number at the index 0 of nums. Same with left and right: they are the minimum and maximum index. Makes sense?

[@juandager5220]

​@@ikthedarchowdhury8947If the target is at an extreme, either on the left or right, the while loop will keep running until left == Right== middle. How do you search for words in a physical thesaurus or dictionary? What happens if you are searching for the first or last word in the entire dictionary? Zzzzzzzuly? Hope this helps!

[@pauljones9150]

@@juandager5220 oh thx 🙏 that helped

[@mehikrt8112]

"l, r=0, len(nums)-1 " can you explain this one ? i guess l=0 , r=0 but len(nums) -1 == ? its not like this r= len(nums) -1 , am i right ? Thank you

[@ashish7936]

nope it means l=0 and r=len(nums)-1 -> which means length of nums array - 1 so that we get last index of nums array and -1 because the index of array start from 0. hope it helps

[@juandager5220]

In Python, you can declare variables like this: Variable1, Variable2 = Value1, Value2 So: L, R = 0, lens(nums) -1 Is the same as: L=0 R=lens(nums) - 1 Does that answer your question?

[@TOUNSI28CSS28GHASSEN]

for the (r+l)//2 problem you can easily do r//2 + l//2 because maths

[@onwa]

Not so. Remember, // is floor-division not float-division. Sometimes they're equal, but not always. E.g. (3+5)//2 = 4 while 3//2 + 5//2 = 1 + 2 = 3

[@ZyneBeatbox]

First :o

[@ninjaturtle205]

this solution gives the wrong answer for me Target = 0 [-5, 0, .....] last iteration, L=0, R=1, Midpoint: (0+1)//2 = 0 since target >nums[midpoint], L = Midpoint +1 = 0 + 1 = 1 now L has become greater than R, and the program returns false.

[@heatchecknyc2142]

Make it while L

[@calebsparks5344]

Anyone else think the l was a 1 and get really confused for a second?

[@juandager5220]

In which line of code? What timestamp? Some solutions: 1. Write full words for variables: left, right 2. Notice how the IDE has different colors for variables and numbers. L is white, 1 is purple. 3. Practice more. And you'll gain intuition.

[@opreastefan5371]

Beautiful!

[@Exploshi]

👑you dropped this

[@liabasqulizad7962]

Thank you sir