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

https://leetcode.com/

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:

nput: 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

 

Code :

var searchRange = function(nums, target) {
    // 시작 위치를 찾는 이진 검색 함수
    function findStart(nums, target) {
        let left = 0;
        let right = nums.length - 1;
        let start = -1;

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

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

        return start;
    }

    // 끝 위치를 찾는 이진 검색 함수
    function findEnd(nums, target) {
        let left = 0;
        let right = nums.length - 1;
        let end = -1;

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

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

        return end;
    }

    const start = findStart(nums, target);
    
    // 시작 위치를 찾지 못한 경우
    if (start === -1) {
        return [-1, -1];
    }
    
    const end = findEnd(nums, target);
    return [start, end];
};

 

Solutions Code :

var searchRange = function(nums, target) {
    let ans = [-1, -1]; // 결과 배열 초기화
    let start = 0, end = nums.length - 1, mid; // 시작 및 끝 인덱스 초기화

    // 첫 번째 발생 위치 찾기
    while (start <= end) { // 시작 인덱스가 끝 인덱스보다 작거나 같을 때까지 반복
        mid = Math.floor((start + end) / 2); // 중간 인덱스 계산
        if (target == nums[mid]) { // 찾으려는 값이 중간 값과 같은 경우
            ans[0] = mid; // 결과 배열의 첫 번째 요소를 중간 인덱스로 설정
            end = mid - 1; // 끝 인덱스를 중간 - 1로 업데이트하여 왼쪽 반복
        } else if (target < nums[mid]) { // 찾으려는 값이 중간 값보다 작은 경우
            end = mid - 1; // 끝 인덱스를 중간 - 1로 업데이트하여 왼쪽 반복
        } else { // 그렇지 않은 경우 (찾으려는 값이 중간 값보다 큰 경우)
            start = mid + 1; // 시작 인덱스를 중간 + 1로 업데이트하여 오른쪽 반복
        }
    }

    // 마지막 발생 위치 찾기
    start = 0; // 시작 인덱스 초기화
    end = nums.length - 1; // 끝 인덱스 초기화
    while (start <= end) { // 시작 인덱스가 끝 인덱스보다 작거나 같을 때까지 반복
        mid = Math.floor((start + end) / 2); // 중간 인덱스 계산
        if (target == nums[mid]) { // 찾으려는 값이 중간 값과 같은 경우
            ans[1] = mid; // 결과 배열의 두 번째 요소를 중간 인덱스로 설정
            start = mid + 1; // 시작 인덱스를 중간 + 1로 업데이트하여 오른쪽 반복
        } else if (target < nums[mid]) { // 찾으려는 값이 중간 값보다 작은 경우
            end = mid - 1; // 끝 인덱스를 중간 - 1로 업데이트하여 왼쪽 반복
        } else { // 그렇지 않은 경우 (찾으려는 값이 중간 값보다 큰 경우)
            start = mid + 1; // 시작 인덱스를 중간 + 1로 업데이트하여 오른쪽 반복
        }
    }

    return ans; // 결과 배열 반환
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode