이분 찾기 (총괄)

2 분 검색 은 기본 알고리즘 이지 만 10% 의 프로그래머 만 bug 가 없 는 코드 를 쓸 수 있 는 것 으로 집계 됐다.오류 의 원인 은 주로 경계 에 대한 선택 과 판정 조건 에 집중 되 어 있 으 며, 조심 하지 않 으 면 경 계 를 넘 거나 순환 하 는 상황 을 초래 할 수 있다.여기 서 다음 과 같이 요약 한다.
표준 판 2 분 찾기: 질서 있 는 (비 내림차 순) 배열 에서 target 값 을 찾 습 니 다. 배열 에서 요소 가 중복 되 지 않 았 습 니 다. target 을 찾 으 면 해당 요소 에 대응 하 는 index 를 되 돌려 주 고 찾 지 못 하면 - 1 을 되 돌려 줍 니 다.
주의 1: start < end 라면 target 이 num [num. length - 1] 과 같 을 때 이 값 을 찾 을 수 없습니다.주의 2: num [mid] > target 이 있 기 때문에 num [index] = target 이 있 으 면 index 는 mid 보다 작 을 것 입 니 다. end = mid 로 쓸 수 있 습 니까?예 를 들 어 num = {1, 2, 5, 7, 9};end = mid 로 쓰 면 start = 0, end = 0 으로 순환 할 때 (즉 num [start] = 1, num [end] = 1 시) mid 는 영원히 0 이 되 고, 이때 end 도 영원히 0 이 되 어 사순환 에 빠진다.target = - 2 를 찾 으 면 프로그램 이 죽 어 가 는 것 이다.
주의 3: num [mid] < target 이기 때문에 num [index] = = target 이 있 으 면 index 는 mid 보다 클 것 입 니 다. start = mid 로 쓸 수 있 습 니까?예 를 들 어 num = {1, 2, 5, 7, 9};start = mid 라 고 쓰 면 start = 3, end = 4 로 순환 할 때 (즉 num [start] = 7, num [end] = 9 시) mid 는 영원히 3 과 같 고, 이때 start 도 영원히 3 과 같 아 사순환 에 빠진다.target = 9 를 찾 으 면 프로그램 이 죽 어 가 는 것 이다.

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //  1
        int mid = start + ((end - start) >> 1); //         ，      
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //  2
        }
        else{
            start = mid + 1; //  3
        }
    }
    return -1;
}

2 분 찾기 변형 1: 질서 있 는 (비 내림차 순) 배열 에서 target 값 을 찾 습 니 다. 배열 에서 요소 가 중복 되 었 을 수 있 습 니 다. target 이 배열 에 대응 하 는 index 의 최소 값 을 찾 으 면 찾 지 못 하면 - 1 로 돌아 갑 니 다.
주의 1: 좌우 로 인접 한 두 수 를 비교 하기 위해 순환 이 끝 날 때 start 와 end 는 1 을 사이 에 두 어야 합 니 다.
주의 2: a). num [mid] = = target 일 때, 이 때 는 mid 로 바로 돌아 갈 수 없습니다. num [mid - 1] 또는 num [mid - 2] 도 target 과 같 을 수 있 으 므 로, 이 때 는 end = mid 를 계속 순환 해 야 합 니 다.b). num [mid] > target 이 있 을 때 num [index] = = target 이 있 으 면 index 는 mid 보다 작 을 것 입 니 다. 원래 이 이치 에 따라 end = mid – 1 을 명령 해 야 하 는데 왜 여기 서 end = mid 를 사용 할 수 있 습 니까?지난 문제 (표준 판) 의 주의 2 를 돌 이 켜 보면 start = end 일 때 만 순환 하 는 상황 이 나타난다.여기 서 while 순환 의 제한 조건 으로 인해 start 와 end 는 영원히 같 을 수 없 기 때문에 end = mid 도 정확 합 니 다.이로부터 우 리 는 a) 와 b) 두 가지 상황 을 합병 할 수 있다.
주의 3: 여 기 는 위의 문제 와 일치 하 니 변화 가 있 을 필요 가 없습니다.그런데 여기 서 start = mid 라 고 쓰 는 것 도 성립 된 거 예요. 왜 죠?다음 문제 의 주의 3, 같은 예 num = {1, 2, 5, 7, 9};위의 문제 에서 start = mid 라 고 쓰 면 start = 3, end = 4 로 순환 할 때 (즉 num [start] = 7, num [end] = 9 시) mid 는 영원히 3 과 같 고 이때 start 도 영원히 3 과 같 아 사순환 에 빠진다.그러나 이 문제 에 서 는 while 의 제한 조건 변화 로 이런 순환 을 피 했다.
주의 4: 여 기 는 왜 num [start] 과 num [end] 가 target 인지 각각 검사 해 야 합 니까?이 두 값 은 모두 target 과 같 을 수 있 기 때문에 중간 2 분 동안 start 와 end 의 업데이트 과정 에 달 려 있 습 니 다.여기 서 몇 가지 간단 한 예 를 마음대로 사용 하면 바로 검증 할 수 있다.순환 이 끝 날 때 num [start] = = num [end] = target 은 제목 에 따라 start 로 돌아 가 야 하기 때문에 start 를 먼저 검증 합 니 다.두 값 이 target 이 아니라면 target 이 존재 하지 않 습 니 다. - 1 로 되 돌아 갑 니 다.

public int binarySearchMinimumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //  1
        int mid = start + ((end - start) >> 1);   //         ，      
        if(num[mid] >= target){ //  2
            end = mid;
        }
        else{
            start = mid + 1; //  3
        }
    }
    if(num[start] == target) //  4
        return start;
    else if(num[end] == target)
        return end;
    else
        return -1;
}

2 분 찾기 변형 2: 질서 있 는 (비 내림차 순) 배열 에서 target 값 을 찾 습 니 다. 배열 에서 요소 가 중복 되 었 을 수 있 습 니 다. target 이 배열 에 대응 하 는 index 의 최대 값 을 찾 으 면 찾 지 못 하면 - 1 로 돌아 갑 니 다.
이 치 는 이전 문제 와 마찬가지 로 주의 2 와 주의 3 곳 에서 위의 문제 와 반대로 하면 된다. 원 리 는 중복 되 지 않 고 정확 하지 않 을 때 몇 개의 간단 한 test case 로 테스트 할 수 있다.

public int binarySearchMaximumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //  1
        int mid = start + ((end - start) >> 1);      //         ，      
        if(num[mid] <= target){ //  2
            start = mid;
        }
        else{
            end = mid - 1; //  3
        }
    }
    if(num[end] == target)
        return end;
    else if(num[start] == target) //  4
        return start;
    else
        return -1;
}

2 분 찾기 변형 3: 질서 있 는 (비 내림차 순) 배열 에서 가능 한 '최대' index 를 찾 아 num [index] < target, 배열 에서 요소 가 중복 되 고 찾 지 못 하면 되 돌아 갑 니 다 - 1.
주의 1: 우 리 는 이 단계 에 대해 따로 고려 할 수 있 습 니 다. num [mid] = target 일 때, 우 리 는 num [index] < target 을 요구 하기 때문에 index 는 mid 왼쪽 에 있어 야 합 니 다.num [mid] > target 일 때 target 은 num [mid] 의 왼쪽 에 있 을 것 입 니 다. 따라서 index 도 mid 의 왼쪽 에 있 을 것 입 니 다.그렇다면 한 걸음 더 생각해 보 자. 만약 num [mid] > = target 을 할 때 우리 가 end = mid 의 조작 을 했다 면 어떤 결 과 를 얻 었 을 까?제 한 된 테스트 를 통 해 문제 가 없 는 것 같 습 니 다. while 의 제한 조건 으로 인해 start + 1 = end 때마다 순환 이 끝 났 기 때문에 표준 판 2 분 검색 에 나타 난 순환 상황 은 존재 하지 않 습 니 다.
주의 2: num [mid] < target 시, 왜 start = mid 가 아 닌 start = mid + 1 을 사용 합 니까?num [mid + 1] = target 이 가능 하기 때문에 이때 start = mid + 1 이면 num [start] = = target 은 정 해 를 놓 쳤 습 니 다.

public int binarySearchClosestFromLeft(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);         //         ，      
        if(num[mid] >= target){ //  1
            end = mid - 1;
        }
        else{ //  2
            start = mid;
        }
    }
    if(num[end] < target){
        return end;
    }
    else if(num[start] < target){
        return start;
    }
    else{
        return -1;
    }
}

2 분 찾기 변형 4: 질서 있 는 (비 내림차 순) 배열 에서 가능 한 '최소' index 를 찾 아 num [index] > target 을 찾 습 니 다. 배열 에서 요소 가 중복 되 고 찾 지 못 하면 되 돌아 갑 니 다 - 1.이 치 는 위의 문제 와 완전히 같 으 니 조금 만 조정 하면 된다.
주의 1: 여 기 는 위의 문제 와 주의 1 원리 가 같 습 니 다. start = mid 로 써 도 문제 가 없 을 것 입 니 다.

public int binarySearchClosestFromRight(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);          //         ，      
        if(num[mid] <= target){
            start = mid + 1; //  1
        }
        else{
            end = mid;
        }
    }
    if(num[start] > target){
        return start;
    }
    else if(num[end] > target){
        return end;
    }
    else{
        return -1;
    }
}

위 에서 말 한 것 을 종합해 보면 규칙 을 정리한다.

배열 에 중복 요소 가 없 을 때: while 순환 판정 조건 은 (start < = end) 이 고 매번 start 가 mid + 1 로 업데이트 되 며 end 는 mid – 1 로 업데이트 된다.

배열 에 중복 요소 가 포함 되 어 있 을 때 또는 찾 아야 할 값 이 target 의 인접 수 일 때 판정 조건 은 (start + 1 < end) 이 고 num [mid] = = target 일 때 mid 로 돌아 가지 않 고 상황 에 따라 새로운 start 또는 end 로 돌아 갑 니 다.start 가 mid 로 업 데 이 트 될 때마다 end 도 mid 로 업데이트 하면 됩 니 다.

원래 주소 링크:https://simpleandstupid.com/2014/12/23/이분 찾기 에 대한 총 결 /