Leetcode 일기: 153. 회전 정렬 배열에서 최소값 찾기 [이진 검색]

이것은 내가 얻는 청중이 아무리 적더라도 계속할 동기를 주기를 바라는 leetcode 질문의 투쟁을 문서화하는 새로운 시리즈입니다.

link

이 질문은 훌륭했습니다. 수정된 이진 검색을 연습하게 되었고 완료하고 다른 사람들이 일반적으로 어떻게 접근했는지 확인한 후 더 나은 것을 얻었습니다! 코드는 논의 중인 것과 동일하지만 내 설명은 더 포괄적입니다.

문제는 회전된 정렬된 배열이 주어지면 O(log n) 효율성으로 최소 수를 찾는 것입니다.
회전된 배열은 모든 인덱스가 이동된 수입니다. 예를 들어 [1,2,3,4,5,6,7,8]의 경우:
[8,1,2,3,4,5,6,7]
[7,8,1,2,3,4,5,6]
[6,7,8,1,2,3,4,5]
이것들은 모두 배열이며, 각각은 이전 인덱스의 1만큼 오른쪽으로 이동합니다.

가능한 경우로 바로 들어가기 전에 먼저 중간 공식이 다음과 같은지 확인하겠습니다. Math.floor((left+right)/2);
사람들이 Math.ceil도 한다고 생각합니다. 저는 바이너리 검색에 대해 배우는 동안 처음 본 버전인 전자를 선택했습니다.

또 다른 규칙인 nums[left]도 반환합니다.

이제 이 문제를 이해했으며 가능한 시나리오를 살펴보겠습니다.
1.) 숫자[중간] > 숫자[오른쪽]:
[3,4,5,6,7,8,1,2]
[2,3,4,5,6,7,8,1]
위의 두 가지가 그러한 예입니다.

이 경우 권리를 찾는 것이 논리적으로 합리적입니다. 중간 값이 올바른 값보다 크면 배열이 중간 지점을 지나 회전했음을 의미하기 때문입니다. 그렇지 않으면 원래 배열에서처럼 mid < 오른쪽을 얻어야 합니다. 따라서 최소값은 중간 인덱스의 오른쪽 어딘가에 있습니다.
이것은 예제에서도 분명하지만 완전성을 위해 설명했습니다. 예제에 의한 증명은 일반적으로 100% 작동하지 않습니다.

이 경우 우리가 해야 할 일은 다음과 같습니다.
왼쪽 = 중간+1.

여기서 +1이 중요합니다! 왼쪽 또는 오른쪽 값에 답이 포함되어 있는 경우 가장자리 케이스를 처리해야 하기 때문입니다. 하지만 이 if 문 내부에서는 오른쪽만 = min일 수 있습니다.
그래서 말이에요

왼쪽 = 0, 오른쪽 = 1, 따라서 중간 = 0
nums[mid] > nums[right]를 만족합니다.
그래서 왼쪽 === 오른쪽, 종료하고 답을 반환할 수 있습니다.

2.) 숫자[중간] <= 숫자[오른쪽]:
[6,7,8,9,1,2,3,4,5]//답 === 중간
[6,7,8,1,2,3,4,5]//답 === 중간
[7,8,9,1,2,3,4,5,6]//답 === 가운데 왼쪽
[7,8,1,2,3,4,5,6]//답 === 가운데 왼쪽

왼쪽을 보면 초기 mid가 정확히 답인 경우도 처리하므로 다음을 수행해야 합니다.
오른쪽 = 중간; 따라서 답변은 프로세스에서 제외되지 않습니다.
이제 봐
[1,2] 반대는 이미 이전에 처리되어 있기 때문에
왼쪽 = 0, 중간 = 0, 오른쪽 = 1
nums[mid] <= nums[right]를 만족합니다.
그리고 right=mid, 그래서 left === mid이고 종료하고 답을 반환합니다.

이제 위에 제공된 예제를 사용하여 두 조건이 어떻게 회전하고 [7,1] 또는 [1,2] 엔드게임을 향해 나아가는지 확인해야 합니다. 아래의 전체 코드:

var findMin = function(nums) {
    let left, right, mid;
    left  = 0;
    right = nums.length-1;

    while (left < right) {
        mid = Math.floor((left+right)/2);
        if(nums[mid] > nums[right]) {
            left = mid+1
        } else {
            right = mid
        }
    }

    return nums[left];
}

내 첫 번째 솔루션은 아래에 있습니다. 코드 자체와 일종의 자체 문서에서 더 체계적이지만 훨씬 더 복잡하고 명시적으로 처리해야 하는 이상한 경우가 있습니다. 면접관이 위의 내용을 더 좋아할 것이라는 것을 알고 있지만 코드가 완전히 완성되지 않은 경우에도 아래에 있는 사람이 많은 점수를 얻을 수 있습니다.

var findMin = function(nums) {
    let mid, start, end, midI, prevI, nextI
    start = 0;
    end = nums.length-1;


    while (start < end) {
        midI = Math.floor((start+end)/2);
        prevI = midI-1 > -1 ? midI-1: nums.length-1;
        nextI = midI+1 === nums.length ? 0 : midI+1;

        mid = nums[midI]

        if(nums[prevI] > mid && mid < nums[nextI]) { //7,0,1
            return mid;
        }

        if(nums[start] > mid && mid < nums[end]) {
            // go toward the bigger end
            if(nums[start] > nums[end]) {
                end = midI-1; 
            } else {
                start = midI+1;
            }
        }

        if(nums[start] <= mid && mid > nums[end]) {
            // go toward the smaller end
            if(nums[start] > nums[end]) {
                start = midI+1;
            } else {
                end = midI-1; 
            }

        }

        if(nums[start] < mid && mid < nums[end]) {
            // go toward start
            end = midI-1;
        }
    }

    return nums[start]
};

nums[start] > mid && mid > nums[end]는 배열이 가장 작은 것에서 가장 큰 것으로 정렬되기 때문에 불가능하다는 점에 유의하십시오.

두 솔루션 간의 주요 개념적 차이점은 하나가 오른쪽을 바라보는 것입니다.
이것은 일종의 직관력이 발달되어야 한다고 생각합니다. 지금까지 가능한 모든 경우를 가장 자세하게 살펴보고 있습니다.

이 글을 읽은 후 생각나는 것이 있으면 알려주세요. 감사합니다!