Imagine array as people line up and facing a wall, whenever a person want to join the queue, we can either choose a person, push him back and sit in front of him, or join at the end of the queue. The natural of array list cause that, we are searching right (I am bigger than you, then I join behind you so i + 1), if we are searching left (I am smaller than you, I don't have to move but push you behind as i). That is why we can always choose the lower bound pointer. At first I am thinking why god create left and right bound unequally.
Approach The problem is little bit modified when compared to finding the floor/ceil of an element using binary search. Usually to find the floor,(Here I am assuming you know the basic binary search concept of finding the floor and ceil) we consider the rightmost search space. if(nums[mid]
one of the things I noticed when solving this problem is that if the target is less than nums[0] you should return 0, and if the target is greater than nums[len(nums)-1], to return len(nums). do you think this is efficient or just a waste of space/time?
@@ravivanam7868ardon me if this is a dumb question but how would the code still work if the target is out of bounds, won't the program stop executing after it returns 0?
left and right pointers define the range in which the target lies. so if left is 3 and right is 12 then the target could be at any index from 3 to 12 including 3 and 12. now imagine what happens when left = right = some number, say 4 then the target could be at any index from 4 to 4 including 4. see it? it means it must be at 4(=left = right).
I am also confused with it. What I understand is that it depends on how you move your boundary. If you don't set the boundary over the mid (e.g left = mid, but not left = mid+1), you should be careful about using
we are updating the range to search here.. if the target is not equal to element at position mid, we can say that it has to lie either on left or right side of mid ,i.e search area will half of the previous. if target is less than mid then we search on left side with right=mid-1 ( we are not considering element at mid because we already checked if target== element at mid) and the other case left=mid+1 if target> element at mid.
for a moment i was feeling really dumb, i tried different ways and stuck for about 45 mins, then i saw ur explaination,, i wonder why this logic didn;t hit me ,, im feeling really dumb😓😓
Cool solution. I only looked at this once i finished my solution. Mine was basically implement binary search, and if it doesnt work, there are 3 cases to take account for. Code: begin = 0 end = len(nums) - 1 last_value = len(nums) - 1 first_index = 0 while begin target: end = midpoint - 1 else: return midpoint
for i in range(len(nums)): if target > nums[last_value]: return last_value + 1 if target < nums[first_index]: return 0 if nums[i] < target < nums[i+1]: return i+ 1
@@Saotsu1 on leetcode it says that the runtime is 102 ms and it beat about 46 percent of submissions. It that slow? I heard that leetcode sometimes give random numbers about submissions
Not me patching up six conditions like the transformers in Transformers 2 that joined together to barely crawl pass through the finish line and guy just does a regular binary search QAQ
i would have never come out with this lol. Maybe, i would have studied computer science and all i did was code and learn a gang of techniques and thrive to always come out with new ways to make algorithms ran faster and more efficient...crazy, respect to you mah software engineeris, programmers or whatever you are. honestly , im happy with iteration throught the entire loop lol Doesn't that make more sense haha. jk, ima memorize this technique like people memorize Maradona and Magico Gonzales tricks and then show the world
💡 BINARY SEARCH PLAYLIST: th-cam.com/video/U8XENwh8Oy8/w-d-xo.html
Nice One! I came here to find out why we are returning left. Thanks brother.
Same here. I am a little confused why we are returning left in the end?
Same here
One o' the best LeetCode channels in YT
Keep them coming! You’re doing a great job
unlike others you had a clear understanding why to use binary search.
that breathing at the end freaked me out lol
Lol damn I dont know how that was left in, it sounds like it was looping a few times
Thanks a lot. The video was really helpful and the way you explain it is so great
like your videos! They are easy to understand.
Imagine array as people line up and facing a wall, whenever a person want to join the queue, we can either choose a person, push him back and sit in front of him, or join at the end of the queue.
The natural of array list cause that, we are searching right (I am bigger than you, then I join behind you so i + 1), if we are searching left (I am smaller than you, I don't have to move but push you behind as i).
That is why we can always choose the lower bound pointer. At first I am thinking why god create left and right bound unequally.
Thank you so much, really helpful and lucid to understand!
Who invents these problems !! Crazy stuff
I did something like this:
def binary(list1, key):
start = 0
end = len(list1) - 1
while start list1[mid]:
start = mid + 1
elif key < list1[mid]:
end = mid - 1
# print(mid)
if key > list1[mid]:
return mid + 1
elif key < list1[mid] and mid > 0:
return mid
else:
return 0
Did exactly this
helpful
wow that trick at the end was *chefs kiss*
Thank you sir. i am kotlin user but its really impressive thank you
great explanation. Very appreciate!!
the line "return l;" is insane, spent 1h+ and couldn
't figure out this line of code
Well explained !
Very well explained like why we should left, why not right??
Thanks a lot❤
Approach
The problem is little bit modified when compared to finding the floor/ceil of an element using binary search. Usually to find the floor,(Here I am assuming you know the basic binary search concept of finding the floor and ceil) we consider the rightmost search space.
if(nums[mid]
Floor of 5 is 4? dafuq
@@_DashingAdi_ Intelligent man, by floor I mean, the closest minimum, big brain time
one of the things I noticed when solving this problem is that if the target is less than nums[0] you should return 0, and if the target is greater than nums[len(nums)-1], to return len(nums). do you think this is efficient or just a waste of space/time?
waste of space and time cuz the code would still work when target is out of bounds
@@ravivanam7868ardon me if this is a dumb question but how would the code still work if the target is out of bounds, won't the program stop executing after it returns 0?
at 12:50, I am still not clear why left becomes 1 since the shift has not occured, so left should remains at 0. Any help with better explantion? thnks
The state where L=R is one step before the algo will end. We have: while(L
I am confused about when to use (less than)< vs
left and right pointers define the range in which the target lies. so if left is 3 and right is 12 then the target could be at any index from 3 to 12 including 3 and 12. now imagine what happens when left = right = some number, say 4 then the target could be at any index from 4 to 4 including 4. see it? it means it must be at 4(=left = right).
I am also confused with it. What I understand is that it depends on how you move your boundary. If you don't set the boundary over the mid (e.g left = mid, but not left = mid+1), you should be careful about using
you are the best ♥
That returning 'left' had me!
for me the hardest is not the algorithm, it is the extreme cases such as nums=[1] and the boundaries. I absolutely hate 0 index!
Thanks you!
you should explain that // will only keep the whole number component
1 liner:
import bisect
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target)
is there a recursive function solution?
Recursive kotlin solution:
fun searchInsert(nums: IntArray, target: Int): Int {
return helper(nums, target, 0, nums.size - 1)
}
private fun helper(nums: IntArray, target: Int, left: Int, right: Int): Int {
val middleIndex = (left + right) / 2
if (nums[middleIndex] == target) return middleIndex
if (left > right) {
return left
}
return if (target > nums[middleIndex]) {
helper(nums, target, middleIndex + 1, right)
} else helper(nums, target, left, middleIndex - 1)
}
Thank you sir
It was really hepful
in case the target does not exist in the array, can we check the target value with the most left and right value first and then do the binary search?
that is O(n) operation, so we cannot check.
the time complexity wouldn't change if you did, but it is unnecessary.
great video. I have one small question though. why do we add or subtract 1 from mid?
we are updating the range to search here.. if the target is not equal to element at position mid, we can say that it has to lie either on left or right side of mid ,i.e search area will half of the previous. if target is less than mid then we search on left side with right=mid-1 ( we are not considering element at mid because we already checked if target== element at mid) and the other case left=mid+1 if target> element at mid.
for a moment i was feeling really dumb, i tried different ways and stuck for about 45 mins, then i saw ur explaination,, i wonder why this logic didn;t hit me ,, im feeling really dumb😓😓
Cool solution. I only looked at this once i finished my solution.
Mine was basically implement binary search, and if it doesnt work, there are 3 cases to take account for.
Code:
begin = 0
end = len(nums) - 1
last_value = len(nums) - 1
first_index = 0
while begin target:
end = midpoint - 1
else:
return midpoint
for i in range(len(nums)):
if target > nums[last_value]:
return last_value + 1
if target < nums[first_index]:
return 0
if nums[i] < target < nums[i+1]:
return i+ 1
thanks
the best
Why not do this:
If target in nums:
Return nums.index(target)
Else:
nums.append(target)
nums.sort()
Return nums.index(target)
This is slow as hell, the purpose is a efficient solution
@@Saotsu1 on leetcode it says that the runtime is 102 ms and it beat about 46 percent of submissions. It that slow?
I heard that leetcode sometimes give random numbers about submissions
@@issamuhsen1245 Your code will run with O(N), which isn't slow, but very slow compared to O(log n)
@@Saotsu1 thanks for help
bro please do a dsa course in python
left you mad man xD. ur the best
Hi 🙂 this solution doesn't work for 👉 nums=[1, 3, 5, 6], target=2 😵💫 What am I missing? 🧐
what if we have duplicate values??
Not me patching up six conditions like the transformers in Transformers 2 that joined together to barely crawl pass through the finish line and guy just does a regular binary search QAQ
When I submit this solution, it beats only 47% in runtime... Why do you think that's the case?
I don't understand the return L part.
i would have never come out with this lol. Maybe, i would have studied computer science and all i did was code and learn a gang of techniques and thrive to always come out with new ways to make algorithms ran faster and more efficient...crazy, respect to you mah software engineeris, programmers or whatever you are. honestly , im happy with iteration throught the entire loop lol Doesn't that make more sense haha. jk, ima memorize this technique like people memorize Maradona and Magico Gonzales tricks and then show the world
Now they specify that they *require* logarithmic time complexity in the problem itself.
Literally. And it's still an easy.
@@doc9448 Yeah, it still is. Because it's a very basic application of binary search.
he's breathing so hard at the end lol. It really is a difficult question though, from a beginner like me at least.
🤑🤑🤑
#completedbyaditi2206
thank u so much!
thank you