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

문제링크: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

정렬된 배열에서 목표값이 들어있는 배열의 범위를 구하는 문제다.

Solution

1. Binary search

이미 정렬되어있는 배열에선 binary search를 통해 O(logn)의 시간복잡도로 목표값을 찾을 수 있다. 목표값의 왼쪽, 오른쪽을 확인해 각각 가장 왼쪽 값인지 오른쪽 값인지 확인해 좌표를 구한다.

Algorithm

• 먼저 기본적인 binary search를 통해 목표값이 있는 범주를 얻는다.
• 목표값이 없으면 루프를 나가고 [-1, -1]을 반환한다.
• 목표값을 찾으면 findFirst를 실행하고 이는 현재값과 왼쪽 값을 비교해 가장 왼쪽 좌표를 찾는다.
• findRight를 실행하고 이는 현재값과 오른쪽 값을 비교해 가장 오른쪽 좌표를 찾는다.
• 찾은 좌표를 반환한다.

var searchRange = function(nums, target) {
  const findFirst = (left, right) => {
    while (left <= right) {
      const mid = parseInt((left + right) / 2);
      if (nums[mid] < target) left = mid + 1;
      else if (nums[mid] > target) right = mid - 1;
      else {
        // Find left most
        if (nums[mid - 1] < target || mid === 0) return mid;
        else right = mid - 1;
      }
    }
  };
  
  const findLast = (left, right) => {
    while (left <= right) {
      const mid = parseInt((left + right) / 2);
      if (nums[mid] < target) left = mid + 1;
      else if (nums[mid] > target) right = mid - 1;
      else {
        // Find right most
        if (nums[mid + 1] > target || mid === nums.length - 1) return mid;
        else left = mid + 1;
      }
    }
  }
  // Sorted Array Binary Search
  // 왼쪽이 목표보다 작은 수
  // 오른쪽이 목표보다 높은 수
  let left = 0, right = nums.length - 1;
  let firstResult = -1;
  let lastResult = -1;
  while (left <= right) {
    const mid = parseInt((left + right) / 2);
    if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1;
    else {
      // Find leftMost and rightMost
      firstResult = findFirst(left, right);
      lastResult = findLast(left, right);
      break;
    }
  }
  return [firstResult, lastResult];
};

시간복잡도 O(logn), 공간복잡도는 재귀를 사용하지 않기 때문에 O(1)을 만족한다. 세 부분의 함수의 동작이 비슷하게 겹치는 부분이 있는 부분을 제외하면 기능 자체는 효율적으로 작동한다.

2. Left most binary search

Binary search함수를 정의할 때 일반적으로는 탐색하려는 값이 존재할 때 바로 루프를 탈출하지만 목표값보다 크거나 같은 부분을 계속 줄여나가는 방식으로 목표값보다 크거나 같은 값 중 가장 왼쪽값을 찾아낼 수 있다. 이 함수를 재사용해 목표값 + 1을 찾으면 목표값+1과 같거나 큰 값중 가장 왼쪽 즉 목표값의 오른쪽 좌표 + 1을 얻을 수 있다.

Algorithm

• nums[mid]가 크거나 같은 경우를 모두 right = mid - 1로 갱신해 같은 값이더라도 가장 왼쪽값을 가리키도록 한다.
• leftIdx를 찾은 후 nums[leftIdx] === target 조건을 통해 값이 존재하는지 검증한다. 없는 경우 [-1, -1] 반환.
• 값이 존재하면 오른쪽좌표를 findLeft(target + 1) - 1을 통해 얻고 결과를 반환한다.

var searchRange = function(nums, target) {
  // leftMost Binary Search
  const findLeft = (target, left=0, right=nums.length) => {
    while (left <= right) {
      const mid = parseInt((left + right) / 2);
      if (nums[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
    return left;
  }
  const leftIdx = findLeft(target);
  // Validation & findRight with findLeft(target + 1)
  return nums[leftIdx] === target ? [leftIdx, findLeft(target + 1) - 1] : [-1, -1]; 
};

목표값이 정수이기 때문에 목표값 + 1을 통해 가장 우측 좌표를 구할 수 있다. 하지만 정수형이 아니라면 사용할 수 없는 알고리즘이다. 1번 알고리즘은 목표값을 빠르게 찾게 되면 바로 탈출할 수 있지만 2번은 항상 O(logn)의 시간을 모두 사용하게 된다. 결과적으로 두 알고리즘 모두 복잡도는 같기 때문에 큰 차이는 없지만 정수형에 한해서는 readable하고 함수를 재사용하는 2번 알고리즘이 좋다고 생각한다.