Given an array of integers 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).

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

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

used 2 binary search to find the begin and end of sub array

I want to recode the way it does a binary search properly:

while(i<j){
            int mid=i+(j-i)/2;
            if(nums[mid]>=target) j=mid;
            else i=mid+1;
}

This way, i will always be <= the targe we want

while(i<j){
                int mid=i+(j-i)/2+1;
                if(nums[mid]>target) j=mid-1;
                else i=mid;
}

We plus one to the mid index, to find the right side of the substring.

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int i=0,j=nums.length-1;
        if(nums.length==0||nums[i]>target||nums[j]<target) return new int[]{-1,-1};
        if(nums[i]==target&&nums[j]==target) return new int[]{i,j};

        int[] res = {-1,-1};

        while(i<j){
            int mid=i+(j-i)/2;
            if(nums[mid]>=target) j=mid;
            else i=mid+1;
        }

        if(nums[i]==target) {
            res[0]=i;

            j=nums.length-1;

            while(i<j){
                int mid=i+(j-i)/2+1;
                if(nums[mid]>target) j=mid-1;
                else i=mid;
            }

            res[1]=i;
        }

        return res;
    }
}

Python version

Reference Source)

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)