Find First and Last Position of Element in Sorted Array - Java Solution

1. Introduction

In this post, we'll tackle a problem from the domain of binary search: finding the first and last position of a given target value in a sorted array. This problem exemplifies the use of binary search to achieve efficient O(log n) runtime complexity in array manipulation.

Problem

Given an array of integers nums, sorted in non-decreasing order, and a target value, the goal is to find the starting and ending position of the target value in the array. If the target is not found, the function should return [-1, -1].

2. Solution Steps

1. Use binary search to find the first occurrence of the target.

2. Use binary search to find the last occurrence of the target.

3. Handle cases where the target is not found.

4. Optimize the searches to maintain O(log n) runtime complexity.

3. Code Program

public class FirstAndLastPosition {
    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = searchRange(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]"); // Test the function
    }

    // Function to find the first and last positions of a target in a sorted array
    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        result[0] = findFirst(nums, target);
        result[1] = findLast(nums, target);
        return result;
    }

    // Helper function to find the first occurrence of the target
    private static int findFirst(int[] nums, int target) {
        int idx = -1;
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
            if (nums[mid] == target) idx = mid;
        }
        return idx;
    }

    // Helper function to find the last occurrence of the target
    private static int findLast(int[] nums, int target) {
        int idx = -1;
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            if (nums[mid] == target) idx = mid;
        }
        return idx;
    }
}

Output:

[3, 4]

Explanation:

1. searchRange: This function uses binary search to find the first and last positions of the target value.

2. findFirst and findLast: These helper functions are specialized versions of binary search. findFirst searches for the first occurrence, and findLast searches for the last occurrence of the target in the array.

3. In both functions, the search space is narrowed down based on whether the target is found, and adjustments are made to locate either the first or last occurrence.

4. These functions return the index of the first and last occurrence of the target, respectively. If the target is not found, -1 is returned.

5. The function ensures O(log n) runtime complexity by efficiently using binary search.