왜 그리고 어떻게?

나는 주어진 정수 배열에서 비감소 순서로 정렬되어 주어진 목표 값의 시작 위치와 끝 위치를 찾는 leetcode에 대한 질문을 해결하는 동안. 따라서 단순 바이너리 스카치를 사용하여 배열에서 대상 요소의 시작과 끝을 반환하는 것은 불가능했습니다. 왜냐하면 해당 요소의 첫 번째, 끝 또는 중간이 될 수 있는 첫 번째 대상 요소를 찾은 인덱스만 반환하기 때문입니다. 그래서 우리는 Double Binary Scarch를 사용하는데, 그 방법은 다음과 같습니다...

접근하다

1. 첫 번째 이진 검색:

   • 이진 검색을 수행하여 대상의 마지막 항목을 찾습니다.
   • 0에서 si(시작 인덱스)로 시작하고 nums.length - 1에서 ei(끝 인덱스)로 시작합니다.
   • 가운데 요소 nums[mid]가 목표보다 작으면 시작 인덱스 si를 mid 1로 이동하여 오른쪽 절반에서 검색합니다.
   • 목표값보다 크면 끝 인덱스 ei를 mid - 1로 이동하여 왼쪽 절반에서 검색합니다.
   • nums[mid]가 대상과 같으면 res[1]을 mid(범위의 현재 끝)로 설정하고 오른쪽 절반(si = mid 1)에서 계속 검색하여 마지막 항목을 찾습니다.

2. 두 번째 이진 검색:

   • 다른 이진 검색을 수행하여 대상의 처음 발생을 찾습니다.
   • si를 0으로, ei를 nums.length - 1로 재설정합니다.
   • 이전과 비슷한 접근 방식을 따르지만 nums[mid]가 대상과 같으면 res[0]을 mid(범위의 현재 시작)로 설정하고 왼쪽 절반(ei = mid - 1)에서 계속 검색하여 첫 번째 항목을 찾습니다.

3. 반품 결과:

   • 결과 배열 res에는 대상 값의 시작 및 끝 인덱스가 포함됩니다.

복잡성

• 시간 복잡도:

  • 처음과 마지막 발생에 대한 이진 검색은 각각 O(log n) 시간이 걸립니다. 두 번의 이진 검색을 수행하므로 전체 시간 복잡도는 O(log n)입니다.

• 공간 복잡성:

  • O(1) 변수에 대해 고정된 양의 추가 공간을 사용하고 있기 때문입니다.

암호

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[1] = mid;  // Update end index
                si = mid   1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}