First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34

0:00 - Read the problem
1:35 - Drawing Explanation
5:15 - Coding Explanation

leetcode 34

#binary #search #python

[MP-nyep]

I watched some 4-5 videos for this problem, but this is hands down the most easiest and intuitive way of solving.
Thanks a ton

[Chirayu]

Initially what I did is finding the element through binary search and then iterating left and right to find leftmost and rightmost. But now I realized in worst case that would be O(N).
Thanks a ton for this video!

[nataliagrigoryeva]

As always, such a great explanation! I have a small suggestion for a slight efficiency boost: if the target is not in the array, we could run the binary search once and set right to -1 if left is -1, without running the binary search a second time.

[aryanyadav]

Using leftBias boolean variable was very clever.

[yalebass]

it makes total sense to use binary search to find the left and rightmost instances if the target, I don’t know why I suddenly let my code return to O(n). Thanks for the vid!

[MsSkip]

Great thanks! Tried tuning a little bit further and start searching after we found initial match but lots of edge cases in that case tbh

[healing]

Thank you. This is better than all leetcode discuss solutions. I don't even think I will forget this one

[nishanttanwar]

Great Explanation, I found the video using the link given in the leetcode post. This solution is so intuitive and is much better than the solution provided with the Leetcode problem. Keep up the good work.

[vikassharma-kydv]

We can optimise it further by finding first index, if not found we need not find second Index

[appcolab]

Wow!! Man, I love this. I was just coming across some complicated solutions but this 🔥, thank you so much!

[ShivangiSingh-wcgk]

The binary search updates were very intutive thank you

[vaibhavdesai]

I was used similar approach but I used binary search exit condition as (nums[mid] == target && nums[mid -1] != target) similarly for right bias it will nums[mid+1] != target. This one is much cleaner

[danielbzhang]

Here's my solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
leftpos, rightpos = -1, -1
l, r = 0, len(nums)-1

while l <= r:
mid = (r+l) // 2
if nums[mid] == target:
while mid-1 >= 0 and nums[mid-1] == target:
mid -= 1
leftpos = mid
while mid+1 <= len(nums)-1 and nums[mid+1] == target:
mid += 1
rightpos = mid
break
if nums[mid] > target:
r = mid - 1
else:
l = mid + 1

return [leftpos, rightpos]

[basic--advance]

Bringing the Algorithms 101

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:

def binary_search_leftmost(A, T):
L = 0
R = len(A)
while L < R:
m = floor((L + R) / 2)
if A[m] < T:
L = m + 1
else:
R = m
return L

def binary_search_rightmost(A, T):
L = 0
R = len(A)
while L < R:
m = floor((L + R) / 2)
if A[m] > T:
R = m
else:
L = m + 1
return R - 1

l = binary_search_leftmost(nums, target)
r = binary_search_rightmost(nums, target)

return [l, r] if target in nums else [-1, -1]

[HR-pzts]

My first approach was binary search and it unfortunately didn't worked and had to switch to linear search and it worked just fine after a few tries with using few conditions and Boolean. And for some reason it was better than 100% java submissions for time complexity.

[eshabaweja]

solved it myself; here to compare and improve :)

[samCoder]

Had I watched your video before my interview, I would have cleared the interview :(

[anandhu]

after r=m-1 and l=m+1, won't it be better if we return if the values in this new position != target? (To stop the search to left(or right) if we already reached left(or right) end)

[chenlee]

This is the best explanation i watched, thank u.

[anshumansharma]

You explain very well. Thanks for working hard on these explanations