[5주차] 이분 탐색 (이진 검색; Binary Search)

이분 탐색 (Binary Search)이란?

개념

1. 정렬된 데이터에서 특정 데이터를 찾을 때 탐색 범위를 절반씩 줄여가며 탐색하는 방법
   • 모든 데이터를 순회하며 확인하는 방식보다 빠름
   • 시간복잡도 \(O(log_2N)\) 
2. 중앙값과 찾으려는 데이터를 비교하여 중앙값의 왼쪽 또는 오른쪽 절반 선택
   • 중앙값 > 탐색 데이터 : 왼쪽
   • 중앙값 < 탐색 데이터 : 오른쪽

구현 패턴

0. 데이터 정렬 (필요 없는 경우도 존재)
1. 탐색 범위 지정
   • low : 0 (또는 초기 탐색 범위의 최소값; 구현 시 편의를 위해 lo로 사용)
   • high : 배열크기 - 1 (또는 초기 탐색 범위의 최대값; 구현시 편의를 위해 hi로 사용)
2. 중앙값 설정
   • mid : (low + high) / 2
3. 중앙값과 비교 
   • arr[mid] == toSearch : 탐색 완료
   • arr[mid] > toSearch : high &eq; mid - 1 (왼쪽 절반)
   • arr[mid] < toSearch : low &eq; mid + 1 (오른쪽 절반)
4. low ≤ high 만족하는 동안 2, 3 반복
   • low > high : 탐색 불가

 

•  

예제 : 수열에서 특정 숫자 찾기

수열에 해당 숫자가 없는 경우

수열에 해당 숫자가 있는 경우

코드

int size = 10;
int numbers[10] = {3, 8, 9, 15, 24, 39, 52, 70, 99, 100};
int binarySearch(int toSearch)
{
    int lo = 0;
    int hi = size - 1;
    int mid;
    while(lo <= hi)
    {
        mid = (lo + hi) / 2;
        if(numbers[mid] == toSearch)
        {
            return mid; // exist at index mid
        }
        else if(numbers[mid] > toSearch) // left half
        {
            hi = mid - 1;
        }
        else // right half
        {
            lo = mid + 1;
        }
    }
    return -1; // not exist
}

https://github.com/ahnyeji/C_Algorithm/blob/main/BinarySearch/example.cpp