Approach:
Step 1 Binary search first
Step 2 Binary search last
Step 3 Return both
Code:
def firstLast(arr,x):
l,h=0,len(arr)-1
f=-1
while l<=h:
m=(l+h)//2
if arr[m]==x:
f=m
h=m-1
elif arr[m]<x:
l=m+1
else:
h=m-1
l,h=0,len(arr)-1
s=-1
while l<=h:
m=(l+h)//2
if arr[m]==x:
s=m
l=m+1
elif arr[m]<x:
l=m+1
else:
h=m-1
return[f,s]
Limitation:
Only works for sorted array
Top comments (0)