Find First and Last Position of Element in Sorted Array

Problem Statement 

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

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

You must write an algorithm with O(log n) runtime complexity.

 

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]

Example 3:

Input: nums = [], target = 0

Output: [-1,-1]

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

Step 1 : – Template Implementation

There are two main Binary Search templates: 1). Inclusive boundary search template (while (low <= high)) 2). Boundary convergence search template (while (low < high))

Based on our analysis of the problem statement, this is a target-based search problem where we need to find specific indices for a given target element. Therefore, we will use the standard inclusive boundary search template (while (low <= high)) as our foundation.

 

Java 
class Solution {
    public int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (param1 == param2) {
                return mid;
            } else if (param1 < param2) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

 

Step 2 : – I/O parameters.

Template input parameters :- To calculate the value of param1, we access the element at index mid, which is nums[mid]. We replace param2 with the target value. Output parameter :- The standard template returns the index mid if the target is found, or -1 if it is not found.

 

Java 
class Solution {
    public int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Step 3 : – Test case scenarios & Directional Search.

In standard Binary Search, returning mid immediately works when finding any single occurrence. However, for an array with duplicates like nums = [5, 7, 7, 8, 8, 10] and target = 8, returning on the first match could give either index 3 or index 4.

To find both the starting and ending boundaries, we introduce our main method searchRange to call our search logic twice:

  • Scenario 1: Finding the First Position (isFirst == true)

    • Test Case: nums = [5, 7, 7, 8, 8, 10], target = 8

    • When mid points to index 4 (nums[4] == 8), we save bound = 4.

    • Since isFirst is true, a target value might exist earlier on the left side.

    • We shrink the right boundary: high = mid - 1.

  • Scenario 2: Finding the Last Position (isFirst == false)

    • Test Case: nums = [5, 7, 7, 8, 8, 10], target = 8

    • When mid points to index 3 (nums[3] == 8), we save bound = 3.

    • Since isFirst is false, a target value might exist later on the right side.

    • We shrink the left boundary: low = mid + 1.

 

Java 
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findBound(nums, target, true);
        int last = findBound(nums, target, false);
        return new int[] { first, last };
    }

    private int findBound(int[] nums, int target, boolean isFirst) {
        int low = 0, high = nums.length - 1;
        int bound = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                bound = mid;
                if (isFirst) {
                    high = mid - 1; // Scenario 1: Search left half for first occurrence
                } else {
                    low = mid + 1;  // Scenario 2: Search right half for last occurrence
                }
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return bound;
    }
}

Step 4: – Handle corner test cases.

We evaluate how the code handles edge cases automatically:

  • Corner Case 1: Empty Array (nums = [], target = 0)

    • high is initialized to -1. The loop condition low <= high (0 <= -1) is false from the start.

    • findBound returns the default bound = -1 for both first and last, resulting in [-1, -1].

  • Corner Case 2: Target Not Present (nums = [5, 7, 7, 8, 8, 10], target = 6)

    • The condition nums[mid] == target is never met during execution.

    • bound remains -1, and the method returns [-1, -1].

 

Java 
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findBound(nums, target, true);
        int last = findBound(nums, target, false);
        return new int[] { first, last };
    }

    private int findBound(int[] nums, int target, boolean isFirst) {
        int low = 0, high = nums.length - 1;
        int bound = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                bound = mid;
                if (isFirst) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return bound;
    }
}

Final Code : – 

 

Java 
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findBound(nums, target, true);
        int last = findBound(nums, target, false);
        return new int[] { first, last };
    }

    private int findBound(int[] nums, int target, boolean isFirst) {
        int low = 0, high = nums.length - 1;
        int bound = -1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (nums[mid] == target) {
                bound = mid;
                if (isFirst) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return bound;
    }
}
Prev
Next
Scroll to Top