Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

Solution: Binary Search

The key lies in how we locate the left and right endpoints.

vector<int> searchRange(vector<int>& nums, int target) {
    int start=0;
    int end=nums.size()-1;
    vector<int> res(2, -1);
    if (end<0) return res;

	// Move end as much as possible for greater or equal cases, lazily move start
    while(start < end) {
        int mid=(start+end)>>1;
        if (nums[mid]<target) start=mid+1;
        else end=mid;
    }

    if (nums[start]!=target) return res;
    else res[0]=start;

    end=nums.size()-1;
    while(start < end) {
		// If both start and end positions equal target, move start right to end the loop
        int mid=((start+end)>>1)+1;
        if (nums[mid]>target) end=mid-1;
        else start=mid;
    }

    res[1]=end;
    return res;
}

#binary-search