C) 이진탐색(binary search) 구현하기

저번 시간에 헀던 순차탐색과 비슷하지만 구조가 조금 다르다. 이번에는 재귀를 사용하여 이진탐색을 구현해보았다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COMPARE(A,B) ((A)>(B))?(1):(((A)<(B))?(-1):(0))

int binsearch(int list[ ], int searchnum, int left, int right) {
	int middle;
	while(left<=right)
	{
	    middle = (left+right)/2;
	    switch (COMPARE(list[middle],searchnum)){
	        case -1: return binsearch(list,searchnum,(middle+1),right);
	        case 0: return middle;
	        case 1: return binsearch(list,searchnum,left,(middle-1));
	    }
	}
	return -1;
}
int prime[]={ ... };
int main()
{
  int search_num;
  int idx;

  scanf("%d", &search_num);
  idx = binsearch(prime,search_num,0,9999);

  printf("%d\n", idx);
}

 

A[0]	A[1]	A[2]	A[3]	A[4]
1	2	3	4	5

위에 배열처럼 1부터 5까지 A라는 배열이 있다고 가정해보자. 그럼 A[0]번쨰배열이 left가 될것이고 A[4]가 배열의 마지막인 right가 될것이다. 그러면 그중간인 A[2]가 middle이 되겠다. 중간값을 찾아가면서 범위를 줄여가며 원하는 숫자가 몇번째에 들어가있는지 찾아주는 것이다. case문을 통해 자기자신의 함수를 불러오는 로직을 가지고있다.