thesarfo

Reference

First and Last Position of an Element

Finding both the first and last index of a target in a sorted array by running a modified binary search twice.

views 0

Given a sorted array and a target, find its first and last index, or [-1,-1] if absent, in O(log n). (LeetCode 34)

Run binary search twice: once continuing left after a match (to find the first occurrence), once continuing right after a match (to find the last).

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};  // Default result if the target is not found.


        if (nums.length == 0) {
            return res;
        }


        // Find the first position of the target
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res[0] = mid;
                right = mid - 1;  // Continue searching on the left side to find the first occurrence
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }


        if (res[0] == -1) {
            return res;
        }


        // Find the last position of the target
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res[1] = mid;
                left = mid + 1;  // Continue searching on the right side to find the last occurrence
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }


        return res;
    }
}