C언어의 이진탐색(binary search) 알고리즘

데이터를 반으로 나눈 후, 중간 값을 이용해 특정 값을 탐색하는 알고리즘이다.

중간 값을 기준으로 작고 큶을 비교해야 하기 때문에 반드시 데이터가 정렬되어 있어야 한다.

추가 응용 방법(알고리즘을 공부하고 싶으신 분들은 다음 사례로 함수를 Customizing해보세요.) 

             1: 내림차순으로 정렬된 데이터에서도 값을 탐색하게 한다.

             2: 특정 수가 아닌, boolean(탐색 여부) 또는 int(탐색하기 위해 반복된 횟수) 값을 리턴하게 한다.

             3: 매개변수의 형태를 변경하여 이진 탐색을 구현

 

#include <stdio.h>

int binary_search(int[], int, int);  // 매개변수: 탐색할 배열, 배열 요소의 개수, 찾으려는 수   
				     // 리턴 값: 해당 수의 위치(인덱스)
int main() {
    int a[10] = { 1, 5, 9, 16, 23, 32, 48, 55, 78 };	// 오름차순 정렬된 9개의 데이터
    
    printf("%d",binary_search(a,9,32));   // 5
    return 0;
}

int binary_search(int arr[], int count, int answer){
    int start = 0;      // 배열의 시작
    int end = count-1;  // 배열 요소의 개수 - 1 = 배열의 마지막 인덱스
    
    while(start<=end){
        int mid = (start+end)/2;  // 현재 배열의 중간
        
        if(arr[mid]==answer){     // 탐색이 성공하면, 그 수의 위치(인덱스)를 리턴
            return mid;
        }else if(arr[mid]>answer){ // 중간 값이 찾으려는 값보다 크면
            end = mid-1;    // 중간 값 바로 이전까지 탐색
        }else{  // 중간 값이 찾으려는 값보다 작으면 
            start = mid+1;  // 중간 값 바로 다음부터 탐색
        }
    }
    
    return -1;  // 찾지 못하면 -1을 리턴
}