# My one binary search solution, but the worst case can be O(n)?

• The idea is :

1. Use binary search to find a target
2. Extend forwards and backwards to find the two boundaries

But when the list if full of target, e.g. [1,1,1,1,1,1,1,1,1,1] to find "1". This solution can be O(n). Does this meet the requirement?

``````class Solution:
# @param A, a list of integers
# @param target, an integer to be searched
# @return a list of length 2, [index1, index2]
def searchRange(self, A, target):
start = 0
end = len(A) - 1
while start <= end:
mid = (start + end) / 2
if A[mid] == target:
start = mid
end = mid
s_mark = False
while A[start] == target:
if start == 0:
s_mark = True
break
else:
start -= 1
if s_mark == False:
start += 1

e_mark = False
while A[end] == target:
if end == len(A) - 1:
e_mark = True
break
else:
end += 1
if e_mark == False:
end -= 1
return [start, end]
elif A[mid] > target:
end = mid - 1
else:
start = mid + 1
return [-1, -1]``````

• If the list is all 1, the initial search should return true immediately when you check the element at the index in the middle.

• You mean I should add some lines to do so? But actually all-1 is just an extreme case, I want to point out that the time complexity will increase with the increasing of number of targets

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.