이진탐색이란?

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

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

1. 첫번째 주소와 마지막 주소의 중간 값인 (0 + 9 )/2 = 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이 찾으려는 값인지를 확인하고 출력합니다.

소스코드

#include<stdio.h>
main(){
int target,low,high,mid;
int data[10] = {2,3,5,7,8,9,11,13,15,20};

scanf("%d",&target);
low = 0; //search대상범위의 첫번째값 
high = 9; //search대상범위의 마지막값

while(1){
	if(low<=high){
		mid=(low+high)/2; //mid값 계산 (소수점이하는 자동으로 절삭)
		
		if(target==data[mid]){
			printf("%d는 %d번째 index에 있습니다.",target,mid);
			break;
		}
		
		if(target<=data[mid]){
			high=mid; //mid값 위 절삭 
		}else{
			low=mid; //mid값 아래 절삭
	 	}
	}else{
		printf("%d는 존재하지 않습니다.",target);
		break;
	}
}