[알고리즘, C] 이진 탐색(Binary Search) 구현

<이진 탐색(Binary Search) 구현>

[BinarySearch.c]

/*
* 알고리즘 - 이진 탐색(Binary Search)
* 파일명: RecursiveBinarySearch.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-27
* 이전 버전 작성 일자:
* 버전 내용: 재귀적으로 구성한 이진 탐색 알고리즘 구현
* 이전 버전 내용:
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int RecursiveBinarySearch(int arr[], int first, int last, int target)
{
	int mid;
	// first보다 last가 커지는 경우 = 값을 찾지 못한 경우 - 재귀의 탈출 조건 첫 번째.
	if (first > last)
		return -1;

	// 이후 첫번째 인덱스와 마지막 인덱스의 절반인 중앙값을 설정한다.
	mid = (first + last) / 2;

	// 탐색 시작
	// 찾은 경우 인덱스 값을 반환 - 재귀의 탈출 조건 두 번째.
	if (target == arr[mid])
		return mid;

	// 값을 찾지 못한 경우
	else if (target > arr[mid]) // 목표로 한 값이 중앙값보다 크다면
		return RecursiveBinarySearch(arr, mid + 1, last, target); // mid 까지는 비교했으므로 mid의 다음 인덱스부터 last까지 다시 탐색
	else // 목표로 한 값이 중앙값보다 작다면
		return RecursiveBinarySearch(arr, first, mid - 1, target); // mid까지는 비교했으므로 first부터 mid의 바로 이전 인덱스까지 다시 탐색 
}


int main()
{
	int arr[] = { 1,3,5,7,9 };
	int input, result;
	printf("찾을 수 : ");
	scanf("%d", &input);
	result = RecursiveBinarySearch(arr, 0, (sizeof(arr) / sizeof(int)) - 1, input);

	if (result == -1)
		printf("찾지 못함\n");
	else
		printf("%d 번째 인덱스에 있음\n", result);


	return 0;
}

 

[탐색을 배우기에 앞서]

이전까지는 계속 정렬에 대해서 공부했다.

전에도 정렬을 왜 배우냐고 했을때, 거기에 이렇게 답을 했었다.

https://sevenshards.tistory.com/15

[알고리즘, C] 버블 정렬(Bubble Sort) 구현

"탐색을 이해하기 위해서는 정렬 알고리즘을 알아야 한다."

자료구조의 3대 연산인 '삽입', '삭제', '탐색(조회)'의 이야기를 하면서 성능까지 따졌었다.

이제는 탐색에 대한 공부를 하게 된다.

하지만 지금 작성하는 이진 탐색이나 다음 글인 보간 탐색과 같은 '알고리즘'이 메인이 아니다.

탐색은 알고리즘보다 '자료구조'에 더 가까운 주제다.

 

"효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안된다.

그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다."

 

그리고 지금까지 배워왔던 자료구조 가운데 탐색에 효율적인 자료구조는 '트리(Tree)'였다.

다음에 작성하게 될 보간 탐색 이후에는 다시 트리와 관련된 글을 올리게 될 것이다.

 

[이진 탐색의 이해]

탐색은 저장된 데이터가 정렬이 되어있는지, 안되어있는지에 따라 사용할 수 있는 알고리즘이 다르다.

내가 지금까지 알고 있는 탐색 알고리즘은 크게 두 가지다.

 

정렬되지 않은 대상을 기반으로 하는 탐색 - 순차 탐색(또는 선형 탐색, Linear Search) → $O(n)$

정렬이 된 대상을 기반으로 하는 탐색 - 이진 탐색(Binary Search) → $O(log_2n)

 

이진 탐색은 정렬이 된 데이터를 기준으로 적용할 수 있는 알고리즘이다.

배열의 인덱스의 시작(first)과 끝(last)을 합해서 2로 나눈 중앙의 값(mid)을 이용하여 목표로 하는 값을 찾는 방식이다.

중앙의 인덱스에 있는 값이 목표 값보다 작다면 first부터 mid-1까지 다시 탐색을 진행.

그와 반대의 경우에는 mid+1부터 last까지 다시 탐색을 진행한다.

그리고 알고리즘 자체가 재귀적이므로 위와 같이 구현하는 것이 가능하다.

 

[이진 탐색의 성능 평가]

이진 탐색의 경우, 데이터의 양이 n일 때 비교 연산의 수행을 거듭할 수록 데이터의 양은 반으로 줄어든다.

그래서 시간 복잡도를 계산하면 $O(log_2n)의 결과가 나오게 된다.