[Algorithm] 이진탐색 알고리즘

이진탐색이란?

이진탐색(이분검색)은 말 그대로 검색할 자료를 반씩 나누어 그 중간값을 찾는 대상값과 비교하는 작업을 반복하여 자료를 찾는 검색을 뜻하며 빠른속도로 자료를 찾을 수 있습니다. 단 이진탐색을 하기위해서는 데이터가 정렬되어있어야 합니다.

 

이진탐색 과정

 

이진탐색을 할 데이터들이 위와 같이 정렬되어있다고 가정하고 숫자 7을 찾는 이진탐색과정을 알아보겠습니다.

 

1. 첫번째 주소와 마지막 주소의 위치를 활용하여 중간 위치를 계산합니다.

중간위치 = (0+9)/2 = 4.5 -> 소수점절삭 -> 4

2. 중간위치 4번째주소에 있는 값 8이 찾으려는 값인지 확인합니다. 7은 8보다 작으므로 찾으려는 값의 범위는 0~4번째 주소입니다.

3. 찾으려는 범위의 첫 번째 주소와 마지막 주소의 위치를 이용하여 중간위치를 계산후 찾으려는 값과 비교합니다.

중간위치 = (0+4)/2 = 2

4. 중간위치 2번쨰 주소에 있는값 5가 찾으려는 값인지 확인합니다. 7은 5보다 크므로 찾으려는 값의 범위는 3~4번째 주소입니다.

5. 찾으려는 범위의 첫 번째 주소와 마지막 주소의 위치를 이용하여 중간위치를 계산후 찾으려는 값과 비교합니다.

중간위치 = (3+4)/2 = 3.5 -> 소수점절삭 -> 3

6. 중간위치 3번째 주소에 있는 값 7이 찾으려는 값인지를 확인하고 출력합니다.

 

C언어 / C++ 코드

#include<stdio.h>
int main() {
    int target,low,high,mid;
    int data[10] = { 2,3,5,7,8,9,11,13,15,20 };
    
    scanf_s("%d", &target);
    low = 0; //search대상범위의 첫번째값 
    high = 9; //search대상범위의 마지막값
    
    while (low <= high) {
        mid = (low + high) / 2;
        if (target == data[mid]) { //탐색 성공
            printf("%d는 %d번째 index에 있습니다.", target, mid);
            return 0;
        }
        else if (target < data[mid]) { // 탐색 범위 재조정 low ~ mid-1
            high = mid - 1;
        }
        else if (target > data[mid]) { // 탐색 범위 재조정 mid+1 ~ high
            low = mid + 1;
        }
    }
    
    printf("%d는 존재하지 않습니다.", target);
    return 0;
}