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.
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😓😓
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
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?
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
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
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.
@@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
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: czcams.com/video/U8XENwh8Oy8/video.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
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
Keep them coming! You’re doing a great job
Thanks a lot. The video was really helpful and the way you explain it is so great
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.
One o' the best LeetCode channels in YT
like your videos! They are easy to understand.
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
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😓😓
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
Thank you sir. i am kotlin user but its really impressive thank you
Who invents these problems !! Crazy stuff
wow that trick at the end was *chefs kiss*
great explanation. Very appreciate!!
1 liner:
import bisect
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target)
Very well explained like why we should left, why not right??
Thanks a lot❤
Well explained !
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
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!
It was really hepful
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?
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
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
Hi 🙂 this solution doesn't work for 👉 nums=[1, 3, 5, 6], target=2 😵💫 What am I missing? 🧐
you should explain that // will only keep the whole number component
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.
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
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)
}
Thanks you!
Thank you sir
you are the best ♥
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.
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
thanks
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
left you mad man xD. ur the best
bro please do a dsa course in python
When I submit this solution, it beats only 47% in runtime... Why do you think that's the case?
what if we have duplicate values??
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.
I don't understand the return L part.
🤑🤑🤑
#completedbyaditi2206
thank you