복잡도

선형 검색 알고리즘의 시간 복잡도 : O(n)

int search(const int a[], int n, int key)
{
	int i = 0;
	while(i < n) {
		if(a[i] == key)
			return i;
		i++;
	}
	return -1;
}

이진 검색의 시간 복잡도 : O(log n)

int bin_search(const int a[], int n, int key)
{
	int pl = 0;
	int pr = n - 1;
	int pc;

	do {
		pc = (pl + pr) / 2;
		if (a[pc] == key)
			return pc;
		else if (a[pc] < key)
			pl = pc + 1;
		else
			pr = pc - 1;
	} while (pl <= pr);

	return -1;
}