Search for a Range

/*
Given a sorted array of integers, 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].
*/

class Solution {
public:
    int binarySearch(int A[], int n, int target)
    {
        int i = 0, j = n - 1;
        
        while (i <= j)
        {
            int m = i + (j - i) / 2;
            
            if (A[m] == target) return m;
            
            if (A[m] > target) j = m - 1;
            
            if (A[m] < target) i = m + 1;
        }
        return -1;
    }
    
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int pos_target = -1;
        
        int left = 0, right = n - 1;
        
        while (left <= right)
        {
            int m = left + (right - left) / 2;
            
            if (A[m] == target) {pos_target = m; break;}
            
            if (A[m] > target) right = m - 1;
            
            if (A[m] < target) left = m + 1;
        }
        
        if (pos_target == -1) return vector<int>{-1, -1};
        
        int start = pos_target, i = left, j = pos_target - 1;
    	while (i <= j)
		{
			int m = i + (j - i) / 2;
			
			if (A[m] == target)
			{
				j = m;
				if (i == j)
				{
					start = i;
					break;
				}
			}
			else
			{
				i = m + 1;
			}
		}
		
		int end = pos_target; i = pos_target + 1, j = right;
		while (i <= j)
		{
			int m = i + (j - i) / 2;
			
			if (A[m] == target)
			{
				i = m;
				if (i == j)
				{
					end = i;
					break;
				}
			}
			else
			{
				j = m - 1;
			}
		}
		
        return vector<int>{start, end};
    }
};

/*
A better approach 
*/

class Solution {
public:
    
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int lower = -1, upper = -1, i = 0, j = n - 1;
        
        //find lowerbound
        while (i <= j)
        {
            int m = i + (j - i) / 2;
            
            if (A[m] == target)
            {
                lower = m;
                j = m - 1;
            }
            else if (A[m] > target)
            {
                j = m - 1;
            }
            else
            {
                i = m + 1;
            }
        }
        
        if (lower == -1) return vector<int>{-1, -1};
        
        i = lower, j = n - 1;
        while (i <= j)
        {
            int m = i + (j - i) / 2;
            
            if (A[m] == target)
            {
                i = m + 1;
                upper = m;
            }
            else
            {
                j = m - 1;
            }
        }
        
        return vector<int>{lower, upper};
    }
};