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

Source link: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Design

nums = [5,7,7,8,8,10], target = 8 → [3,4]

The idea of this problem is to find find and last position of element separately. The key process is shown as below:

  1. Separate into two functions, which one of these is responsible for searching the starting position of the target, and the other one is for searching the ending position of the target.
  2. For searching the starting position of the target, apply the simple binary search approach. If the target is smaller or equals to the middle point, drop the right part of the range, otherwise, drop the left part.
  3. For searching the ending position of the target, apply the approach what the last step mentioned. If the target is greater or equals to the middle point, drop the left part of the range, otherwise, drop the right part.

Implementation

class Solution {
  public int[] searchRange(int[] nums, int target) {
    int[] res = new int[2];
    res[0] = findFirstPosOfElement(nums, target);
    res[1] = findLastPosOfElement(nums, target);
    return res;
  }

  private int findFirstPosOfElement(int[] nums, int target) {
    int index = -1;

    int left = 0, right = nums.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (target <= nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
      if (target == nums[mid]) index = mid;
    }

    return index;
  }

  private int findLastPosOfElement(int[] nums, int target) {
    int index = -1;

    int left = 0, right = nums.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (target >= nums[mid]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
      if (target == nums[mid]) index = mid;
    }

    return index;
  }
}

Complexity Analysis

Time: $O(logn)$

Space: $O(1)$