수다닷컴

자료구조 과제, 정말 하나도 모르겠습니다 ㅠㅠbinsearch() 알고리즘을 C 언어로 구현해 보라.

배열 a[]는 65,536개의 데이터를 저장할 수 있도록 선언하고,

1부터 65,536까지의 정수값을 순서대로 저장하라.

임의로 선택한 10개의 탐색 키에 대해 비교 횟수가 얼마나 되는 측정해 보고,

시간 복잡도가 O(log n)이 되는지 확인해 보라.

여기서log는 2를 밑으로 하는 로그 함수이다.따라서 log 65,536 = 16 이다.

질문 내용 :

#include stdio.h
#define N 65536
int binsearch(int a[],int key,int left,int right)
{
int mid;
if (left = right) {
mid = (left + right) / 2;
if (key == a[mid]) return mid;
else if(key a[mid]) return binsearch(a, key, left, mid-1);
else return binsearch(a, key, mid+1, right);
}
else return -1;
}
void main()
{
int i, key, result;
int a[N];
for (i = 0; i N; i++)
a[i] = i+1;
printf(탐색 키 입력 : );
scanf_s(%d, &key);
result = binsearch(a, key, 0, 65535);
if (result 0) printf(탐색 키가 없습니다.\n);
else printf(탐색 키를 찾았습니다.\n);
}

여기까지 작성하였는데요;
count함수 이용해서 시간복잡도와 같게 나오는지 비교해보는 문제입니다;
복학생이라 그런지 정말 하나도 모르겠거든요 ㅠㅠㅠ 부탁드립니다 IV

신청하기