이진탐색 == 이분탐색 (Binary Search) 이란?

이진탐색

정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. (정렬된 배열, 리스트에 적합한)

• 배열의 중앙에 있는 값을 조사하여, 찾고자하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는 지를 알아내어 탐색의 범위를 반으로 줄입니다.
• 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있습니다.
• 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합합니다.

 

 

https://minhamina.tistory.com/127

이진탐색의 시간 복잡도
한 번 확인할 때마다 확인하는 원소의 개수가 절반 씩 줄어든다는 점에서 시간 복잡도가 O(logN)입니다.

 

예시

1. 10억 명의 어떠한 이름이 저장되어있는 배열에서 이진 탐색을 이용해 특정한 이름을 찾는 경우

2. 영어 사전에서 단어를 찾는 과정

3. 고정되어 있는 데이터 배열에서 원하는 값을 찾을 경우.

 

또한,

코딩 테스트에서 탐색 범위(2000만 이상)가 큰 상황에선 이진 탐색으로 문제를 접근해보는 게 좋습니다.

> 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면, 이진 탐색과 같이 O(logN)의 속도를 내야하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많습니다. 

 

 

이진 탐색 구현

이진 탐색은 2 가지의 방법으로 구현할 수 있습니다

 

1. 재귀적 방법

// 재귀적 탐색
static int binarySearch(int key, int low, int high, int[] searchInRange) {
    int mid;
    if (low <= high) {
        mid = (low + high) / 2;
        if (key == searchInRange[mid]) return 1;
        else if (key < searchInRange[mid]) return binarySearch(key, low, mid - 1, searchInRange);
        else return binarySearch(key, mid + 1, high, searchInRange);
    }
    return 0;
}

2. 반복적 방법

// 반복적 탐색
static int binarySearch2(int key, int low, int high, int[] searchInRange) {
    int mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if(key == searchInRange[mid]) return 1;
        else if(key < searchInRange[mid]) high = mid - 1;
        else low = mid + 1;
    }

    return 0; 
}

 

구현 시 체크 할 부분

while 문을 이용해서 쉽게 구현할 수 있는데, 이 때 디테일을 잘못 구현하게 되면 특정 상황에서 무한 루프를 돌면서 이분 탐색이 종료하지 않을 수도 있습니다. 따라서 주의해야 합니다.

 

백준 1920 문제

1920번: 수 찾기

 

위 문제로 구현 연습하면 좋을 거 같습니다.

 

맨 위가 반복적 방법이고, 아래 있는 게 재귀적 방법입니다.

메모리와 시간 복잡도 차이는 크게 느끼지 못했습니다.