Binary Search - Find First and Last Position of Element

Problem Statement

Given a sorted array of integers and a target value, find the first and last positions of the target in the array. Return [-1, -1] if the target is not found. This is a medium-level problem that leverages binary search to achieve efficiency in a sorted array.

Example

Input: nums = [5, 7, 7, 8, 8, 10], target = 8

Output: [3, 4] (8 appears from index 3 to 4)

Input: nums = [5, 7, 7, 8, 8, 10], target = 6

Output: [-1, -1] (6 is not in the array)

Code

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = findFirst(nums, target);
        if (result[0] != -1) {
            result[1] = findLast(nums, target);
        }
        return result;
    }
    
    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int first = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                first = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return first;
    }
    
    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int last = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                last = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return last;
    }
}
            

def search_range(nums, target):
    def find_first(nums, target):
        left, right = 0, len(nums) - 1
        first = -1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                first = mid
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return first
    
    def find_last(nums, target):
        left, right = 0, len(nums) - 1
        last = -1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                last = mid
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return last
    
    first = find_first(nums, target)
    last = find_last(nums, target) if first != -1 else -1
    return [first, last]

# Example usage
print(search_range([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
print(search_range([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]
            

function searchRange(nums, target) {
    function findFirst(nums, target) {
        let left = 0, right = nums.length - 1;
        let first = -1;
        
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                first = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return first;
    }
    
    function findLast(nums, target) {
        let left = 0, right = nums.length - 1;
        let last = -1;
        
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                last = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return last;
    }
    
    const first = findFirst(nums, target);
    const last = first !== -1 ? findLast(nums, target) : -1;
    return [first, last];
}

// Example usage
console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]
            

Explanation

• Use two binary searches: one to find the first occurrence, one for the last.
• For the first position, if target is found, search left half to find the earliest occurrence.
• For the last position, if target is found, search right half to find the latest occurrence.
• Adjust pointers based on whether mid element is less than, equal to, or greater than target.
• Return [-1, -1] if target isn’t found; otherwise, return the range.

Note