## 34. Find First and Last Position of Element in Sorted Array

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(logn).

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

Example 1:

``````Input:
nums = [5,7,7,8,8,10], target = 8

Output: [3,4]
``````

Example 2:

``````Input:
nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]
``````

Thoughts:

1. Two binary searches: Search left as target - 0.5, right as target + 0.5
2. Two binary searches:
3. Divide and Conquer with early breaks

a variety of ways to solve the problem

Code: Solution 1: T O(logn)

``````class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
def binarySearch(nums, target):
l, h = 0, len(nums) -1
while l <= h: # NEED this because of single input e.g: , 1
mid = l + (h - l >>1)
if nums[mid] > target:
h = mid - 1
elif nums[mid] < target:
l = mid + 1
return l # MUST BE L to slide over

left = target - 0.5
right = target + 0.5
l, r = binarySearch(nums, left), binarySearch(nums, right)
if l == r: return [-1, -1]
return [l, r - 1]
``````

Code: Solution 2: T O(logn)

``````class Solution(object):
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
if not len(nums):
return [-1, -1]
lo = search(target)
return [lo, search(target+1)-1] if  lo < len(nums) and nums[lo] == target else [-1, -1] # in is to present index out of bounds. e.g: input = []; [2,2]; 3
``````

C++

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ret(2, -1);
if (nums.size() == 0) return ret;
int n = nums.size();
int i = 0, j = n - 1;
// Search for the left one
while (i < j)
{
int mid = (i + j) /2;
if (nums[mid] < target) i = mid + 1;
// else if (nums[mid] > target) j = mid - 1;
else j = mid;
}
if (nums[i]!=target) return ret;
else ret = i;

// Search for the right one
j = n-1;  // We don't have to set i to 0 the second time.
while (i < j)
{
int mid = (i + j) /2 + 1;    // Make mid biased to the right
if (nums[mid] > target) j = mid - 1;
// else if (nums[mid] < target) i = mid + 1;
else i = mid;                // So that this won't make the search range stuck.
}
ret = j;
return ret;
}
};
``````

Python

``````class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
res = [-1,-1]
if not nums: return res

i, j = 0, len(nums) - 1

while i < j:
mid = i + (j - i >> 1)
if nums[mid] < target:
i = mid + 1
else:
j = mid

if nums[i] != target: return res
res, j = i, len(nums) -1

while i < j:
mid = i + (j - i + 1)/2
if nums[mid] > target:
j = mid - 1
else:
i = mid
res = j

return res
``````

Code: Divide and Conquer with early breaks

``````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, r]
return [-1, -1]
return search(0, len(nums)-1)
``````