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

Your algorithm’s runtime complexity must be in the order of O(log n).

# Binary search, twice

The O(log n ) run time combined with the sorted array tell us to use binary search. Maybe twice.

## The first binary search to find the first occurrence of the target

The normal binary search will stop after nums[mid] == target. EG: [0,3,3,3,3], t = 3. We will stop at index 2. To keep the binary search going, we will search again in [0:mid – 1]. If we didn’t find any occurrence in the range, that means the previous found target is the first occurrence.

## The second bs finds the last occurrence of the target

Same as above but search repeatedly in [mid + 1: end]

# Recursive code

```
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
We will call modified binary search twice. Once search leftmost and once search rightmost
"""
first = self.find_first(nums, target, 0, len(nums) - 1)
last = self.find_last(nums, target, 0, len(nums) - 1)
return (first,last)
def find_first(self, nums, target, start, end):
"""
"""
if not nums: return -1
if nums[start] == target:
return start
if start == end:
return -1
mid = start + (end - start) // 2
if nums[mid] >= target:
return self.find_first(nums, target, start, mid)
else:
return self.find_first(nums, target, mid + 1, end)
def find_last(self, nums, target, start, end):
if not nums: return -1
if nums[end] == target:
return end
if start == end:
return -1
mid = end - (end - start) // 2
if nums[mid] <= target:
return self.find_last(nums, target, mid, end)
else:
return self.find_last(nums, target, start, mid - 1)
```

### Take out return statement when nums[mid] == target

We change it from basic binary search by taking out the return statement when we found nums[mid] == target. This allow us to keep searching.

## Find first

### mid = start + (end – start) // 2

With this formula for mid, mid will be at the center when the number of numbers is odd. And mid will **be at the left of the middle when we have a even number of numbers**. This is because we calculate middle using *start* and add the floor of half of the length.

This helps terminate the code when we don’t have any target in the range.

- find_first(nums, target, mid + 1, end) will terminate as usual binary search since mid + 1 will cross end
- find_first(nums, target, start, mid) If we use mid = end – (end – start) // 2, then it won’t terminate if we recursively call this function. An example is [2,3,4] target = 0. We will call : find_first(nums, 0, 0, 2) find_first(nums, 0, 0, 1) find_first(nums, 0, 0, 1) for many times

This problem will be solved if we let mid = start + (end – start) // 2.

### If found a target, maintain it in the range by searching again in [start, mid] instead of [start, mid – 1]

This allow us to have at least 1 occurrence of target to “fall back” on.

### Return start if nums[start] == target

After many recursive calls, our effective range will have 4 conditions

- [target, target] nums[start] is definitely the first target. So we return it
- [not target, target] Let’s assume they have index k and k + 1. mid = k and we will call find_first(nums, target, k, k) and it nums[k] == target. We indeed return the first occurrence of the target
- [target, not target] nums[start] == target, so return start
- [not target, not target] It will return -1

So in all 4 situation, if nums[start] == target, and we return, this will lead to correct behavior.

## Find last

It is almost identical to find first. But we need to change the recursive call conditions and the calculation of mid.

### mid = end – ( end – start) // 2

So we can let let mid squeeze to the back in the case of even length range. This will allow use to terminate.