34. Find First and Last Position of Element in Sorted Array

#binary-search

Problem

Find First and Last Position of Element in Sorted Array - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
  /**
   * This method finds the first and last positions of a target value in a sorted array.
   *
   * @param nums The sorted integer array to search in.
   * @param target The target value to search for.
   * @return An integer array containing the first and last positions of the target,
   *         or [-1, -1] if the target is not found in the array.
   */
  public int[] searchRange(int[] nums, int target) {

    // Find the first position using a separate helper function
    int firstPos = getPosition(nums, target, true);

    // Find the last position using the same helper function with a flag
    int lastPos = getPosition(nums, target, false);

    // Return an array containing the first and last positions
    return new int[]{firstPos, lastPos};
  }

  /**
   * This helper function finds the position of the target value in a sorted array,
   * considering whether to find the first occurrence or the last occurrence.
   *
   * @param nums The sorted integer array to search in.
   * @param target The target value to search for.
   * @param isFirst A flag indicating whether to search for the first occurrence (true)
   *                or the last occurrence (false).
   * @return The index of the target position, or -1 if not found.
   */
  public int getPosition(int[] nums, int target, boolean isFirst) {

    // Initialize low and high pointers for binary search
    int low = 0;
    int high = nums.length - 1;
    int result = -1;

    // Loop until the low pointer crosses the high pointer (search space exhausted)
    while (low <= high) {

      // Calculate the middle index to check
      int mid = low + (high - low) / 2;

      // Check if the target is found at the middle index
      if (nums[mid] == target) {
        // Target found, update result and adjust search space based on isFirst flag
        result = mid;
        if (isFirst) {
          // For first occurrence, keep searching left for a stricter first position
          high = mid - 1;
        } else {
          // For last occurrence, keep searching right for a later last position
          low = mid + 1;
        }
      } else if (nums[mid] < target) {
        // Search right half for the target
        low = mid + 1;
      } else {
        // Search left half for the target
        high = mid - 1;
      }
    }

    // Target not found in the entire search space
    // Return -1 to indicate not found
    return result;
  }
}