# Time complexity of finding range of target in sorted array – Is this solution O(N) in the worst case?

I was going through LeetCode problem 34. Find First and Last Position of Element in Sorted Array, which says:

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value.

If `target` is not found in the array, return `[-1, -1]`.

You must write an algorithm with `O(log n)` runtime complexity.

Since the question wanted `logn` run-time, I implemented the binary-search logic. But I am not sure, and think that, with the extra-while loop inside the base condition, I actually go to `O(n)` in the worst case. Is that true?

``````class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = 0
right = len(nums) - 1
pos = [-1,-1]

while left <= right:
middle = (left + right) // 2
"""
This is pure binary search until we hit the target. Once
we have hit the target, we expand towards left and right
until we find the number equal to the target.
"""
if nums[middle] == target:
rIndex = middle
while rIndex + 1 < len(nums) and nums[rIndex + 1] == target:
rIndex += 1
pos = rIndex

lIndex = middle
while lIndex - 1 >= 0 and nums[lIndex - 1] == target:
lIndex -= 1
pos = lIndex
break

elif target > nums[middle]:
left = middle + 1
else:
right = middle - 1

return pos
``````

Here is what I think for an example array that looks like:

``````input = [8,8,8,8,8,8,8] , target = 8
``````

When the base condition `nums[middle] == target` hits, I will need to iterate the complete array and this makes it run-time complexity as `O(n)`, right?

Interestingly, this solution is faster than 95% of the submissions!! But I think there is some issue with LeetCode!!!

### >Solution :

Yes, you are right, the loop degrades the worst case time complexity. You rightly identified what happens when the input array has only duplicates of the target value, and no other value.

The solution is to perform two binary searches: one that prefers going to the left side, and one that prefers to go to the right side of the target value.

If the test cases do not thoroughly test this O(n) behaviour, this O(n) solution will not come out as a bad one.