이분 탐색

이분 탐색

 

: 정렬된 숫자들의 중간값과 target 값을 비교하여 탐색 범위를 절반씩 줄여가는 알고리즘

 

※ 중간값 = (a+b)/2 

이분 탐색 시 소수점 이하는 내림하여 중간값을 구함

 

출처:https://adjh54.tistory.com/187

 

시간복잡도 : O(log n) 
(새로 정렬해야 하면 O(nlogn))
 
연산마다 탐색 범위를 절반 줄이므로 모든 숫자들을 선형 탐색하는 것보다 상대적으로 빠르다
 

 

코드

 

• 기본

while (left <= right){
    int mid = (right - left) / 2 + left; 
    
    if (target > arr[mid]){ // target 값이 배열 중간값보다 크면
        left = mid + 1; // 우측 탐색
    } else if (target < arr[mid]){
        right = mid - 1; // 좌측 탐색
    } else {
        return mid; 
    }
}

return -1;

 

while문 안에서 target 값과 배열 내 중간값을 비교해 좌측 또는 우측 절반씩 탐색 범위를 줄여가는 코드이다.

 

 

 

• upper bound : target 값보다 처음으로 큰 값이 나오는 위치 탐색

 

출처:https://yoongrammer.tistory.com/105

 

 

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

return right;

 

 

 

• lower bound : target 값의 시작 위치 탐색

 

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

return right;

 
 

헷갈렸던 부분

 

이분탐색 시 while문의 부등호 여부에 따라 right에는 mid 또는 mid -1을 대입하는데 left에는 mid를 대입하지 않는다.

mid를 left에 대입하지 않는 것은 마지막 두 원소를 탐색할 때를 고려해야 하기 때문이다. mid는 (left+right)/2로 내림 계산되므로, 원소가 2개 남았을 때 left(=mid), right 식으로 구성된다. 이때 left에 같은 값인 mid를 계속 대입해봤자 반복문을 탈출 못 하고 무한루프된다.

cf) right = mid
원소 2개가 남았을 때, right에 mid를 대입하면 left와 값이 같아지므로 반복문을 탈출할 수 있다.
 
 
 

• 참고

https://adjh54.tistory.com/187
https://witch.work/posts/binary-search-next-step
https://yoongrammer.tistory.com/105
https://blossoming-man.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%EA%B2%BD%EA%B3%84-%EC%84%A4%EC%A0%95%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%B4%EC%95%BC-%ED%95%98%EB%8A%94%EA%B0%80
https://jackpot53.tistory.com/m/33