[C] 탐색

1. 정렬되지 않은 배열의 순차 탐색

처음부터 마지막까지 하나씩 검사

int sequential_search(int* list, int key, int p, int q)  // p: 맨 처음, q: 맨 마지막 
{
	for (int i = p; i <= q; i++)
		if (list[i] == key)
			return i;   // 탐색 성공
	return -1;          // 탐색 실패
}

2. 정렬된 배열의 순차 탐색

정렬이 되어있으므로 만약 key 값 보다 큰 원소를 발견한다면 탐색 실패

int sequential_search(int* list, int key, int p, int q) 
{
	for (int i = p; i <= q; i++) {
		if (list[i] > key)
			return -1;      // 탐색 실패
		if (list[i] == key)
			return i;       // 탐색 성공 
	}
}

3. 이진 탐색

배열의 중간 값과 key 값을 비교하여 key 값이 더 크면 그 뒷 부분만을, key 값이 더 작으면 그 앞 부분만을 탐색하게 함

int binary_search(int* list, int key, int p, int r)
{
	int q = (p + r) / 2;                 // p: 처음, q: 중간, r: 끝

	if (p <= r) {
		if (key == list[q]) return q;
		else if (key < list[q])
			binary_search(list, key, p, q - 1);
		else if (key > list[q])
			binary_search(list, key, q + 1, r);
	}
	return -1;
}