def searchRange(self, A, B): if B in A: t1=A.index(B) A=A[::-1] t2=A.index(B) return [t1,len(A)-t2-1] return [-1,-1]
This is O(n) not O(log n) as required in description
How do you know when it is an O (n) or O (logn) solution? thnks!!
CPython implementation of index() method is O(n) since it compares the given key with every value in the list starting from index 0 and returns the first index where key-value pair matches. So for a list of length n, it will make n compares in the worst case (key your are looking for is at index = len(list)-1) implying worst case time complexity of O(n). You are using index() twice to find the index of first and last occurrence of given number in the list, thus your code will take 2n time in the worst case, making it O(n) and not O(logn).