이진탐색(binary_search)

이진탐색 : 찾고자 하는 값과 정렬된 데이터의 중앙의 위치한 원소를 비교하면서 탐색 대상을 절반씩 줄여나가는 방법

탐색 방법 중에 '순차탐색'과 '이진탐색' 방법이 있다.

순차탐색

순차탐색은 배열의 원소를 순서대로 하나씩 꺼내서 찾고자 하는 값과 비교하며 원하는 값을 탐색하고, 탐색하려고 하는 대상이 정렬이 되어 있지 않은 경우라면유일하게 사용할 수 있는 탐색 방법이다.
평균적으로 탐색에 소요되는 시간 : n / 2 번

이진탐색

이진탐색을 사용하기 전에는 꼭 정렬이 되어 있어야 하고, 찾고자 하는 값과 정렬된 데이터의 중앙의 위치한 원소를 비교하면서 탐색 대상을 절반씩 줄여나가는 탐색 방법이다. 데이터가 커지면 커질수록 연산의 횟수는 급격히 작아진다.

그림

코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 15

void makeArray(int A[]){ // 배열 만드는 함수
    int i, j;
	srand(time(NULL));
    for(i = 0; i < SIZE; i++)
    	A[i] = rand() % 100; // 중복 제거 안 함
    	/* 중복을 제거하고 싶은 경우
    	for(j = 0; j < i; j++){
    	    if(A[i] == A[j])
    	        i--;
    	} 
    	*/
}

void printArray(int A[]){ // 배열 출력 함수
    for(int i = 0; i < SIZE; i++)
        printf("[%d] ", A[i]);
    printf("\n\n");
}

void insertion_sort(int A[], int n){ // 삽입정렬 - 이진탐색하려면 정렬되어 있어야 함
    int key, i, j;
    for(int i = 1; i < n; i++){ 
        key = A[i]; 
        for(j = i - 1; j >= 0 && A[j] > key; j--) 
            A[j + 1] = A[j]; 
        A[j + 1] = key; 
    }
}

int binary_search(int A[], int key){ // 이진탐색 - 탐색된 key의 인덱스를 return
    int low = 0, high, middle;
    high = SIZE - 1; // high의 인덱스
    while(low <= high) { // low > high이면 더이상 탐색할 공간이 없음
        middle = (low + high) / 2;
        if(key == A[middle]) // 찾는값 == 중간값
            return middle;
        else if(key > A[middle]) // 값 > 중간값
            low = middle + 1; // middle을 기준으로 오른쪽에서 값을 탐색해야 하니까
        else // 값 < 중간값
            high = middle - 1; // middle을 기준으로 왼쪽에서 값을 탐색해야 하니까
    }
    return -1; // 찾는 값이 없는 경우
}

void main(){
    int list[SIZE]; 
    makeArray(list); 
    printArray(list); // 정렬되기 전
    getchar();
    insertion_sort(list, SIZE);
    printArray(list); // 정렬된 후
    
    printf("탐색할 값을 입력하세요 : ");
    int key;
    scanf("%d", &key); // 탐색할 값
    int result = binary_search(list, key);
    if(result == -1)
        printf("찾는 값이 없습니다.\n");
    else
        printf("탐색 결과 => %d 인덱스\n", result);
}