LeetCode Find First and Last Position of Element in Sorted Array (JavaScript), 이분 탐색

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

문제 설명

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 <= 105
• 109 <= nums[i] <= 109
• nums is a non-decreasing array.
• 109 <= target <= 109

---

문제 풀이

이분 탐색(Binary search) 알고리즘을 이용하여 O(logN)으로 해결

target의 가장 작은 index, 가장 큰 index를 찾기 위해 기존 이분 탐색에서 추가된 부분

-> nums[mid] === target인 경우 반복문을 멈추는게 아닌 더 작은 값, 더 큰 값을 찾기 위해 left, right를 조정

• 가장 작은 인덱스(startIndex) 구하기
  • nums[mid] === target이라면 더 작은 값을 구하기 위해 right를 mid - 1로 조정 -> 현재 기준(mid)에서 좌측 구간을 탐색하기 위해
• 가장 큰 인덱스(endIndex) 구하기
  • nums[mid] === target이라면 더 큰 값을 구하기 위해 left를 mid + 1로 조정 -> 현재 기준(mid)에서 우측 구간을 탐색하기 위해

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const find_index = (nums, target, isStart) => {
        let left = 0;
        let right = nums.length - 1;
        let findIndex = -1;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);

            if (nums[mid] === target) {
                findIndex = mid;

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

        return findIndex;
    }

    const startIndex = find_index(nums, target, true);
    const endIndex = find_index(nums, target, false);

    return [startIndex, endIndex];
};

---

결론

이분 탐색(Binary Search) 알고리즘을 이용하여 문제를 해결

문제의 핵심은 target과 같은 값을 발견했을 때 반복을 멈추는게 아닌 더 작거나 큰 값을 찾기 위해 left, right 값을 조정하는 로직을 작성하는 것