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

Given an array of integersnumssorted in ascending order, find the starting and ending position of a giventargetvalue.

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