Solution 1 : **Divide and Conquer with early breaks** : 56 ms

The O(log n) time isn't quite obvious, so I'll explain it below. Or you can take the challenge and prove it yourself :-)

```
def searchRange(self, nums, target):
def search(lo, hi):
if nums[lo] == target == nums[hi]:
return [lo, hi]
if nums[lo] <= target <= nums[hi]:
mid = (lo + hi) / 2
l, r = search(lo, mid), search(mid+1, hi)
return max(l, r) if -1 in l+r else [l[0], r[1]]
return [-1, -1]
return search(0, len(nums)-1)
```

The `search`

helper function returns an index range just like the requested `searchRange`

function, but only searches in `nums[lo..hi]`

. It first compares the end points and immediately returns `[lo, hi]`

if that whole part of `nums`

is full of `target`

, and immediately returns `[-1, -1]`

if `target`

is outside the range. The interesting case is when `target`

can be in the range but doesn't fill it completely.

In that case, we split the range in left and right half, solve them recursively, and combine their results appropriately. Why doesn't this explode exponentially? Well, let's call the numbers in the left half `A, ..., B`

and the numbers in the right half `C, ..., D`

. Now if one of them immediately return their `[lo, hi]`

or `[-1, -1]`

, then this doesn't explode. And if neither immediately returns, that means we have `A <= target <= B`

and `C <= target <= D`

. And since `nums`

is sorted, we actually have `target <= B <= C <= target`

, so `B = C = target`

. **The left half thus ends with target and the right half starts with it.** I highlight that because it's important. Now consider what happens further. The left half gets halved again. Call the middle elements

`a`

and `b`

, so the left half is `A, ..., a, b, ..., B`

. Then `a <= target`

and:- If
`a < target`

, then the call analyzing`A, ..., a`

immediately returns`[-1, -1]`

and we only look further into`b, ..., B`

**which is again a part that ends with**.`target`

- If
`a == target`

, then`a = b = ... = B = target`

and thus the call analyzing`b, ..., B`

immediately returns its`[lo, hi]`

and we only look further into`A, ..., a`

**which is again a part that ends with**.`target`

Same for the right half `C, ..., D`

. So in the beginning of the search, as long as `target`

is only in at most one of the two halves (so the other immediately stops), we have a single path. And if we ever come across the case where `target`

is in both halves, then we split into *two* paths, but then each of those remains a single path. And both paths are only O(log n) long, so we have overall runtime O(log n).

This is btw based on us917's solution.

Solution 2 : **Two binary searches** : 56 ms

```
def searchRange(self, nums, target):
def search(n):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] >= n:
hi = mid
else:
lo = mid + 1
return lo
lo = search(target)
return [lo, search(target+1)-1] if target in nums[lo:lo+1] else [-1, -1]
```

Here, my helper function is a simple binary search, telling me the first index where I could insert a number `n`

into `nums`

to keep it sorted. Thus, if `nums`

contains `target`

, I can find the first occurrence with `search(target)`

. I do that, and if `target`

isn't actually there, then I return `[-1, -1]`

. Otherwise, I ask `search(target+1)`

, which tells me the first index where I could insert `target+1`

, which of course is one index behind the last index containing `target`

, so all I have left to do is subtract 1.

Solution 3 : **Two binary searches, using the library**

Binary search is so good and common that many languages have it in their standard library and you just need to figure out how to apply it to the problem at hand.

**Python:**

```
def searchRange(self, nums, target):
lo = bisect.bisect_left(nums, target)
return [lo, bisect.bisect(nums, target)-1] if target in nums[lo:lo+1] else [-1, -1]
```

**C++:**

```
vector<int> searchRange(vector<int>& nums, int target) {
auto bounds = equal_range(nums.begin(), nums.end(), target);
if (bounds.first == bounds.second)
return {-1, -1};
return {bounds.first - nums.begin(), bounds.second - nums.begin() - 1};
}
```

Or:

```
vector<int> searchRange(vector<int>& nums, int target) {
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (lo == nums.size() || nums[lo] != target)
return {-1, -1};
int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
return {lo, hi};
}
```

**Java:**

Well, Java decided to be annoying and offer `Arrays.binSearch`

but with *"If the array contains multiple elements with the specified value, there is no guarantee which one will be found"*. So it's useless for us. I'm not good at Java, though, so maybe I'm overlooking a way to still make it work. If you manage to do so, please let me know.