이진탐색

이진탐색이란 절반씩 나누어 검색하는 분할탐색 알고리즘을 말한다.

순차탐색보다 빠르며, 이진탐색을 하기 위해서는, 오름차순이나 내림차순으로 정렬된 배열이 필요하다.

이를 간단한 예제로 구현하면 다음과 같다.

#include <stdio.h>
int main(void)
{
    int key;
    int low=0, high, mid;
    int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    scanf("%d", &key);
    high = sizeof(arr) / 4;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key < arr[mid])
        {
            high = mid - 1;
        }
        else if (key > arr[mid])
        {
            low = mid + 1;
        }
        else
        {
            printf("%d번째\n", mid+1);
            break;
        }
    }
 
}
 
 
 

탐색 순서는 다음과 같다.

1.

반복문에서 처리하며, 탐색범위의 끝인 high 가 범위의 처음인 low 보다 작다면 찾는 데이터가

 없는것으로 간주하고 반복문을 종료한다.

2.

mid 는 배열의 중앙값을 나타내는것으로써, 탐색범위의 처음인 low 와 끝인 high 을

 더하여 2로 나눈값이다.

3.

배열의 중앙값과 찾는데이터값을 비교하여, 찾는데이터값 > 중앙값 이라면, 탐색범위의 처음인 low 가 mid+1 로 탐색 범위를 줄이고,

그 반대라면 탐색범위의 끝인 high 가 mid-1로 범위를 줄인다.

첫번째도, 두번째도 아니라면, 값이 같은걸로 간주하고 그 값이 있는 위치를 반환한다.

4.

그 값이 있는 위치를 반환하지 않았다면, 3의 바뀐 low, high, mid 를 가지고 반복한다.

카카오스토리트위터페이스북