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

Problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

---

Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] result = new int[2];
        if (nums == null || nums.length == 0)
            return new int[]{-1, -1};
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
            	left = mid + 1;
            else
            	right = mid;
        }
        if (nums[left] == target)
        	result[0] = left;
        else
            result[0] = -1;
        right = nums.length - 1;
        while (left < right) {
            int mid = (left + (right - left) / 2) + 1;
            if (target < nums[mid])
            	right = mid - 1;
            else
            	left = mid;
        }   
        if (nums[right] == target)
        	result[1] = right;
        else
            result[1] = -1;
        return result;
    }
}

배열이 오름차순으로 정렬되어 있기 때문에, 배열을 반으로 잘랐을 때, 버려지는 부분을 찾을 수 있다. 배열을 반으로 잘라서 왼쪽부터 target을 찾고, 오른쪽부터 target을 찾는다. 왼쪽 target을 찾고, 오른쪽 target을 찾는다.

Explanation

• 다음과 같은 조건은 이진 탐색을 통해 만족시킬 수 있다.

  You must write an algorithm with `O(log n)` runtime complexity.
  

• 이진 탐색을 위해 배열 내 두 요소를 참조할 두 변수 left와 right를 선언하고, 결과 반환을 위한 배열 result를 선언한다.

  int left = 0;
  int right = nums.length - 1;
  int[] result = new int[2];
  

• 먼저 target이 처음 등장하는 위치를 이진 탐색을 통해 찾기 위해 while반복문을 작성한다.
• while반복문이 모두 진행되면 변수 left, right 둘 다 target이 처음 등장하는 위치를 가리키게 된다.

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

• 배열 result의 첫 번째 요소에 while반복문을 통해 얻은 변수 left, right 중 하나를 if조건문으로 할당해준다.

  if (nums[left] == target)
    result[0] = left;
  else
    result[0] = -1;
  

• target이 마지막에 등장하는 위치는 현재 변수 left가 참조하는 위치보다 뒤에 존재하므로, 변수 left값은 그대로 두고, 변수 right값을 처음 값으로 초기화해준다.

  right = nums.length - 1;
  

• target이 처음 등장하는 위치와 마찬가지로 마지막에 등장하는 위치 또한 while반복문을 통해 구해준다.
• while반복문이 모두 진행되면 변수 left, right 둘 다 target이 마지막에 등장하는 위치를 가리키게 된다.

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

• 배열 result의 두 번째 요소에 while반복문을 통해 얻은 변수 left, right 중 하나를 if조건문으로 할당해준다.

  if (nums[right] == target)
    result[1] = right;
  else
    result[1] = -1;
  

• 배열 nums의 요소가 null이거나 길이가 0인 경우 while반복문에 들어갈 수 없고, 반환해야 하는 값이 정해져 있으므로 if조건문을 상단에 작성하여 처리한다.

  if (nums == null || nums.length == 0)
    return new int[]{-1, -1};
  

• 만들어진 배열 result를 반환한다.

  return result;