Finding First and Last Position in Sorted Array Using Java

A popular technical interview task for software engineering roles is finding the minimum and maximum index values that contain a target element within a sorted array.

Step 1

First we call on the find() function which we have created near the bottom of our block of code.

Step 2

Next we must check if the array is empty or if the array even contains the target element that we are searching for. If not, we simply return a negative index value for the min and max positions of the target element in the array.

Step 3

Now it is time to define the find() function that we called on earlier. We must accept a target parameter (T), an array to iterate through (arr), as well as the starting left index value (L). We set the right pointer index value equal to the length of the array minus one since array index values begin with zero rather than one.

Step 4

While the left index pointer value is less than the right index pointer value, we set the middle value equal to the value of the left pointer plus the right pointer after performing the bitwise operation.

Step 5

If the middle index value in the array is less than the target, then we know that the target value we are searching for must exist in the second half of the array. This means iterating through the first half of the array would be completely useless, so we set the left pointer’s index value equal to the middle pointer value plus one.

If the middle index value is greater than the target, we know that the target value must exist within the first half of the array. It would be pointless to iterate through the second half of the array so we set the right pointer’s index value equal to the middle index value minus one.

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        //Step 1
        int left = find(target, nums, 0);
        
        //Step 2
        if (left == nums.length || nums[left] != target) return new int[] {-1, -1};
        
        return new int[] {left, find(target+1, nums, left) -1};
    }
    
//Step 3
    public int find(int T, int[] arr, int L) {
        int right = arr.length - 1;
        
//Step 4
        while (L <= right) {
            int mid = L + right >> 1;
            
//Step 5
           if (arr[mid] < T) L = mid + 1;
            else right = mid - 1;
        }
        return L;
    }
    
}

One More Thing

For business inquiries or general questions feel free to reach me at officialnatelee@gmail.com