C/C++ 2진 탐색(Binary Search) 예제 코드

이진탐색(2진탐색)은 정렬된 데이터에서 원하는 데이터를 빠르게 찾는 방식이다.

예를들어 1부터 100까지 숫자가 있다면 75를 찾아 보자.

일반적인 방식은 1부터 하나하나 데이터를 비교해가며 찾아야 한다.

O(N)에 복잡도를 가진다.

하지만 2진탐색을 사용하면 가장 중간데이터인 50부터 찾아서 비교해보고 50보다 찾아야 할 데이터인 75보다 작다.

그래서 50보다 큰수이기 때문에 50과 가장끝 데이터인 100중 가장 중간 데이터인 75를 비교해본다.

이렇게 중간데이터를 가지고 대소비교를 해가면서 데이터를 찾으면 

O(logN) 의 복잡도를 가진다.

훨씬 빠른 데이터 탐색을 할 수 있다.

코드 구현역시 간단한 편이다.

아래는 이진탐색 예제 코드이다.

아래와 같이 반복문을 가지고 시작과 끝부분의 데이터를 바꿔가며 찾는 방식이 있으며 재귀함수로도 구현이 가능 하다.

#include<stdio.h>
 
//size 크기의 data배열안에서 d를 찾기
//값이없으면 -1반환
//값이 있으면 data배열의 index 반환
int binarySearch(int data[], int size, int d)
{
    int s = 0; //시작
    int e = size - 1; //끝
    int m;
    while (s <= e) {
        m = (s + e) / 2;
        if (data[m] == d) return m;
        else if (data[m] > d) e = m - 1;
        else s = m + 1;
    }
    return -1;
}
 
int main() {
    int data[] = { 1,3,6,8,11,23,111,114,213 };
    int dataSize = sizeof(data) / sizeof(int);
    int ans = binarySearch(data, dataSize, 114);
    printf("%d\n", ans);
}