# 9-11 lines O(log n)

• 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.

• I really like the first Divide and Conquer solution and the proof of its running time. I rewrite it in C++ and it achieves the fastest running time (12 ms) among the C++ codes :-)

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
return search(nums, 0, n - 1, target);
}
private:
vector<int> search(vector<int>& nums, int l, int r, int target) {
if (nums[l] == target && nums[r] == target) return {l, r};
if (nums[l] <= target && target <= nums[r]) {
int mid = l + ((r - l) >> 1);
vector<int> left = search(nums, l, mid, target);
vector<int> right = search(nums, mid  +1, r, target);
if (left[0] == -1) return right;
if (right[0] == -1) return left;
return {left[0], right[1]};
}
return {-1, -1};
}
};
``````

BTW, thanks to the great C++ 11 features of vector initialization using `{}`, which saves a lot of codes :-)

Update: an absolutely high-quality post. I read through all the solutions and learn a lot from them, the algorithm, the proof, and the details of the codes. Thanks a lot!

• It actually took me some time to discover the `target in nums[lo:lo+1]` in Solution 2 :-)

• Thanks for sharing and this is my JAVA version for divide and conquer method:

``````public int[] searchRange(int[] nums, int target) {
return helper(nums, target, 0, nums.length - 1);
}
private int[] helper(int[] nums, int target, int lo, int hi) {
if (nums[lo] == target && nums[hi] == target) return new int[]{lo, hi};
if (nums[lo] <= target && nums[hi] >= target) {
int mid = lo + (hi - lo) / 2;
int[] left = helper(nums, target, lo, mid);
int[] right = helper(nums, target, mid + 1, hi);
if (left[0] == -1) return right;
if (right[0] == -1) return left;
return new int[]{left[0], right[1]};
}
return new int[]{-1, -1};
}
``````

• Three solutions, and in different languages... Bravo!

Could you explain this line please - return max(l, r) if -1 in l+r else [l[0], r[1]]?

• @gudnm What part of it is unclear? It's all pretty basic stuff...

• if -1 in l+r doesn't make sense to me... thanks!

• `l` and `r` are the results for the left and right half, so that just tests whether one of them is doesn't contain the target (e.g., if `l+r` is `[3, 5, -1, -1]`).

• I saw a lot of your brilliant solutions.
I have a question about the coding style in a lot of your code.
What's the benefit of having function inside function in comparison with write another function at same level?
Just like the search and searchRange inthis question.

It seems like the nums and target is shared between search and searchRange?

``````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)
``````

• Hello, I have a question. The function in List is O(N) , when I use it in my code like this:
if target not in nums:
return [-1,-1]
else:
return [bisect.bisect_left(nums,target),bisect.bisect_right(nums,target)-1]
it still accepted......why?

• thanks for sharing!!!
the C++ code can't pass the testcase:
[-1]
0
I think it needs to consider the case that 'target' bigger than all integers in 'array'
so the following code is better:

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return vector<int>{-1,-1};
auto bounds = equal_range(nums.begin(), nums.end(), target);
return *bounds.first != target ||  bounds.first-nums.begin()>=nums.size() ? vector<int> {-1, -1} :
vector<int> {bounds.first - nums.begin(),
bounds.second - nums.begin() - 1};
/*        if(nums.empty()) return vector<int>{-1,-1};
auto low = lower_bound(nums.begin(),nums.end(),target);
if(*low == target && low-nums.begin()<nums.size())
return vector<int>{low-nums.begin(),upper_bound(nums.begin(),nums.end(),target)-nums.begin()-1};
return vector<int>{-1,-1};
*/    }
};``````

• @jianchao.li.fighter very nice, thank you

• @Dexter_GUO Oh wow, what was I thinking? I shouldn't blindly access `*bounds.first` at all, as that's undefined/dangerous if `bounds.first` is `nums.end()`. You shouldn't, either. Thanks, I fixed my C++ solutions. And removed the unnecessary "`vector<int>`" in the return values while I was at it.

• My naive approach.

``````public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int [] { -1, -1 };
int low = 0, high = nums.length - 1;
while (low + 1 < high) {
int mid = (low + high) >>> 1;
if (nums [mid] >= target) high = mid;
else low = mid;
}
int first = (nums [low] == target) ? low : (nums [high] == target ? high : -1);
low = 0; high = nums.length - 1;
while (low + 1 < high) {
int mid = (low + high) >>> 1;
if (nums [mid] > target) high = mid;
else low = mid;
}
int last = (nums [high] == target) ? high : (nums [low] == target ? low : -1);
return new int [] { first, last };
}
``````

• @mdhu Thanks for sharing the Solution. Need to add base condition to pass all test cases.

public int[] searchRange(int[] nums, int target) {
if(nums==null || nums.length==0) return new int[]{-1,-1};
return helper(nums, target, 0, (nums.length-1));
}

• @StefanPochmann " return max(l, r) if -1 in l+r else [l[0], r[1]] ". looks like this expression can return different type of output depending on condition it satisfies. like if -1 in l+r ( is l and r a list ? ), then it returns max(l,r) is that return a list of max integer ??.

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