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.
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
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).
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
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
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
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
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🥲
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
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
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
You can but it’s more efficient to do L + (R-L) // 2 And usually these little details don’t particularly matter but since it’s an overflow problem, the numbers you’re working with are so large that those little intricacies matter a lot. They can change a program from usable to destructive.
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 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?
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?
@@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!
(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.
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
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?
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
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?
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.
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.
Thanks for mentioning the integer overflow problem!
This kind of attention to detail is what separates great from just good.
It's fascinating how beginner friendly this explanation was despite how professional you are, thank you
Always good to practice the basics! I am just happy to recieve a notification from neetcode :d
gotta do the classics sometimes
can't thank you enough for ur tutorials! it's for sure in depth and easy to digest!
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.
Thank You!
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
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).
The best explain to beginner including the integer overflow I ever seen
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
My data structures professor secretly gets his entire lectures from your videos! Except you explain things much better lol. Thanks for all your help!
Hi,
Is there a pattern or a rule when choosing whether l
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
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
that log n breakdown just helped me for sure !
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
i would recc u do them in pattern order rather than randomly. This will help u truly understand the pattern and retain it.
Grokking the coding interview is the answer you are looking for
Review old solutions or topics you've done every other day.
Use Anki to make flash cards. It’ll drill you every day using Spaced Repetition.
@@scvkurt03 how would the problems/solutions translate to cards?
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
TIL how we get log n complexity..
Ah, neetcode doing the daily leetcode challenge 🥺🏆
you are legend bro😄
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🥲
this comment cleared that up for me, thanks!
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
Thank you for the video! Is there a way to do this with recursion??? Thanks!
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
Thank you, your explanation is amazing
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
OMG thank you very much for your channel!
Thank you very much
Thank you. love it!
In leetcode,I tried it and got wrong answer for
nums = [4,5,6,7,0,1,2] , target = 0.output is -1 but expected is 4.Can u please help me?
Can you explain, why it should be
l=mid+1 or r=mid-1 not l=mid or r=mid
Since we know mid is not the target, it will be redundant to include it in the next window.
Thanks, neetcode.
Thank you!
that was great!
Thank you sir
For the overflow couldnt you also do (L // 2) + (R//2)
You can but it’s more efficient to do L + (R-L) // 2
And usually these little details don’t particularly matter but since it’s an overflow problem, the numbers you’re working with are so large that those little intricacies matter a lot. They can change a program from usable to destructive.
How can the list be added in the program????
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
The while condition is L
@@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?
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?
@@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!
@@juandager5220 oh thx 🙏 that helped
can we make the variable names more explanatory?
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
(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.
m=l+(r-l)//2 sorry@@eteran23
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
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?
"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
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
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?
understood
nice
First :o
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.
Make it while L
@@heatchecknyc2142 yes
👑you dropped this
Anyone else think the l was a 1 and get really confused for a second?
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.
for the (r+l)//2 problem you can easily do r//2 + l//2 because maths
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
Beautiful!
#completedbyaditi2206
thank you sir