[알고리즘 총화] 2 점 찾기

2 분 검색 법 은 흔히 볼 수 있 는 검색 방법 으로서 원래 선형 시간 을 대수 시간 범위 로 끌 어 올 려 검색 시간 을 크게 단축 시 켰 으 나 질서 있 는 데이터 에서 찾 아야 한 다 는 전제 가 있다.
2 점 찾기 는 쓰기 쉽 지만 쓰기 가 쉽 지 않 습 니 다. 통계 에 따 르 면 10% 의 프로그래머 만 bug 가 없 는 2 점 찾기 코드 를 쓸 수 있 습 니 다.오류 원인 은 판정 조건 과 경계 값 의 선택 에 집중 되 어 있 기 때문에 경 계 를 넘 거나 순환 하 는 상황 을 초래 하기 쉽다.
다음은 2 분 의 검색 과 변형 에 대해 정리 하 겠 습 니 다.
1. 가장 기본 적 인 2 점 찾기

public int binarySearch(int[] A, int target, int n){
    int low = 0, high = n, mid;
    while(low <= high){
        mid = low + (high - low) / 2;
        if(A[mid] == target){
            return mid;
        }else if(A[mid] > target){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}

그 중 몇 가지 주의해 야 할 점 이 있다.

순환 의 판정 조건 은: low <= high

수치 가 넘 치 는 것 을 방지 하기 위해 mid = low + (high - low)/2

땡  A[mid] 과 같 지 않 을 때 target 또는 high = mid - 1

leetcode 참조: 검색 삽입 위치
2. 목표 값 영역의 왼쪽 경 계 를 찾 습 니 다. / 목표 값 과 같은 첫 번 째 위 치 를 찾 습 니 다. / 목표 값 보다 작 지 않 은 첫 번 째 위 치 를 찾 습 니 다.
A = [1,3,3,5, 7 ,7,7,7,8,14,14] target = 7 return 4

public int binarySearchLowerBound(int[] A, int target, int n){
    int low = 0, high = n, mid;
    while(low <= high){
        mid = low + (high - low) / 2;
        if(target <= A[mid]){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    if(low < A.length && A[low] == target)
        return low;
    else
        return -1;
}

3. 목표치 영역의 오른쪽 경 계 를 찾 습 니 다. / 목표치 와 같은 마지막 위 치 를 찾 습 니 다. / 목표치 보다 크 지 않 은 마지막 위 치 를 찾 습 니 다.
A = [1,3,3,5,7,7,7, 7 ,8,14,14] target = 7 return 7

public int binarySearchUpperBound(int[] A, int target, int n){
    int low = 0, high = n, mid;
    while(low <= high){
        mid = low + (high - low) / 2;
        if(target >= A[mid]){
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
    if(high >= 0 && A[high] == target)
        return high;
    else
        return -1;
}

이 문 제 는 변형 가능 low = mid + 1 으로 우 리 는 마지막 으로 목표치 보다 크 지 않 은 수 를 찾 았 다. 그러면 한 명 더 뒤로 들 어가 서 / 로 돌아 가 는 것 이 목표치 보다 큰 첫 번 째 수 이다.
검 지 offer: 정렬 배열 에 숫자 가 나타 나 는 횟수
4. 마지막 으로 목표치 보다 작은 숫자 찾기 / 목표치 보다 작 지만 목표치 에 가장 가 까 운 숫자 찾기
이 문 제 는 두 번 째 문제 에서 변형 할 수 있 습 니 다. 우 리 는 목표 치 구역 의 아래 (왼쪽) 경 계 를 찾 았 습 니 다. 그러면 다시 한 번 왼쪽으로 물 러 나 는 것 이 목표 치 보다 작은 숫자 입 니 다.사실 high + 1 도 순환 종료 후 low - 1 의 값 이기 때문이다.  low - 1 는 마침 high 과 같 고 high 보다 작 기 때문에 while 순환 이 끝났다.우 리 는 low - 1 국경 을 넘 었 는 지 판단 하기 만 하면 된다.
A = [1,3,3, 5 ,7,7,7,7,8,14,14] target = 7 return 3

int low = 0, high = n, mid;
while(low <= high){
    mid = low + (high - low) / 2;
    if(target <= A[mid]){
        high = mid - 1;
    }else{
        low = mid + 1;
    }
}
return high < 0 ? -1 : high;

5. 목표치 보다 큰 첫 번 째 숫자 찾기 / 목표치 보다 크 지만 목표치 에 가장 가 까 운 숫자 찾기
이 문 제 는 세 번 째 문제 에서 변형 할 수 있 는 것 으로 우 리 는 목표 치 구역 의 상 (우) 경 계 를 찾 았 다. 그러면 다시 오른쪽으로 한 자리, 즉 low 가 목표 치 보다 큰 첫 번 째 숫자 이다.사실 high 도 순환 종료 후 high + 1 의 값 이기 때문이다.  high + 1 는 마침 low 과 같 고 low 보다 크 기 때문에 while 순환 이 끝난다.우 리 는 high + 1 국경 을 넘 었 는 지 판단 하기 만 하면 된다.
A = [1,3,3,5,7,7,7,7, 8 ,14,14] target = 7 return 8

int low = 0, high = n, mid;
while(low <= high){
    mid = low + (high - low) / 2;
    if(target >= A[mid]){
        low = mid + 1;
    }else{
        high = mid - 1;
    }
}
return low > n ? -1 : low;

6. 회전 배열 에서 최소 요 소 를 되 돌려 줍 니 다.
6.1 회전 배열 의 최소 요 소 를 찾 습 니 다 (중복 숫자 가 존재 하지 않 는 다 고 가정)
LeetCode: Find Minimum in Rotated Sorted Array Input: [3,4,5,1,2] Output: 1

public int findMin(int[] nums) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;

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

여기 와 이전의 2 분 에서 찾 은 몇 가지 차이 점 을 주의 하 세 요.

순환 판정 조건 은 high, 등호

가 없다.

순환 에서 nums [left] 와 num [mid] 의 값 을 비교 하여 mid 가 있 는 위 치 를 판단 합 니 다.

만약 low 에 앞부분 이 질서 가 있 고 최소 치가 후반 부분 에 있 음 을 나타 낸다. 령 left < right;

만약 nums[mid] > nums[right] 에 최소 치가 앞부분 에 있다 는 것 을 의미한다.

마지막 으로 left 는 최소 값 요소 가 있 는 위 치 를 가리킨다.
6.2 회전 배열 의 최소 요 소 를 찾 습 니 다 (중복 항목 이 존재 합 니 다)
LeetCode: Find Minimum in Rotated Sorted Array II 검 지 offer: 회전 배열 의 최소 숫자 입력: [2, 2, 2, 0, 1] 출력: 0

public int findMin(int[] nums) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;
    while(left < right){
        mid = left + (right - left) / 2;
        if(nums[mid] > nums[right])
            left = mid + 1;
        else if(nums[mid] < nums[right])
            right = mid;
        else
            right--;
    }
    return nums[left];
}

이전 과 중복 항목 이 존재 하지 않 는 차 이 는 left = mid + 1 일 때 최소 값 이  nums[mid] <= num[right] 왼쪽 이 든 오른쪽 이 든 우 리 는 오른쪽 경 계 를 1 로 줄 입 니 다.
7. 회전 정렬 배열 에서 검색
7.1 중복 항목 을 고려 하지 않 음
LeetCode: Search in Rotated Sorted Array
법 1:

먼저 방법 6.1 을 이용 하여 배열 의 최소 요 소 를 찾 는 것, 즉 분계 점 의 위 치 를 확정 하 는 것

회전 하 는 배열 을 오프셋 으로 하고 right = mid 으로 진실 한 mid 의 위 치 를 구한다.

그리고 2 점 으로 목표치 찾기

public int search(int[] nums, int target) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;
    while(left < right){
        mid = left + (right - left) / 2;
        if(nums[mid] > nums[right])
            left = mid + 1;
        else
            right = mid;
    }
    int offset = left;
    left = 0;
    right = len - 1;
    while(left <= right){
        mid = left + (right - left) / 2;
        int realmid = (mid + offset) % len;
        if(nums[realmid] == target)
            return realmid;
        else if(nums[realmid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

법 2: 사실 회전 배열 의 경계 점 을 찾 을 필요 가 없습니다. 왼쪽 이나 오른쪽 을 검색 할 때 저 희 는 mid 와 high 의 요소 크기 에 따라 판단 할 수 있 습 니 다. target 의 값 에 따라 2 분 검색 을 하면 됩 니 다.

public int search(int[] nums, int target) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        else if(nums[left] <= nums[mid]){
            if(target < nums[mid] && target >= nums[left])
                right = mid - 1;
            else
                left = mid + 1;
        }else if(nums[mid] <= nums[right]){
            if(target > nums[mid] && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}

7.2 중복 항목 존재
LeetCode: Search in Rotated Sorted Array II

public boolean search(int[] nums, int target) {
    int len = nums.length;
    if(len == 0)
        return false;
    int left = 0, right = len - 1, mid;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return true;
        else if(nums[mid] > nums[right]){
            if(target < nums[mid] && target >= nums[left])
                right = mid;
            else
                left = mid + 1;
        }else if(nums[mid] < nums[right]){
            if(target > nums[mid] && target <= nums[right])
                left = mid + 1;
            else
                right = mid;
        }else{
            right --;
        }   
    }
    return false;
}

8. 2 차원 배열 에서 찾기
검 지 offer: 2 차원 배열 에서 찾기
2 차원 배열 은 질서 가 있 고 오른쪽 상단 을 보면 왼쪽 숫자 로 점점 줄 어 들 고 아래 숫자 로 점점 증가한다.따라서 이분 으로 찾 을 수 있 는 사상 을 이용 하여 오른쪽 상단 에서 출발 할 수 있다.

오른쪽 상단 숫자 보다 숫자 가 클 때 아래로 이동 합 니 다.

오른쪽 상단 보다 숫자 시간 을 찾 으 려 면 왼쪽으로 이동 합 니 다.