[알고리즘] 이진 탐색 (개념, 배열 동작 방식, C언어 bsearch함수)

💻 오늘의 목표 : 리스트 완전 정복

 

😊 오늘 할 알고리즘 공부는 이진 탐색 😊

 

[이진 탐색 (Binary Search)]

[이진 탐색의 개념]

• 정렬된 데이터에서 사용할 수 있는 탐색 알고리즘
• 속도가 매우 빠르다.
• 탐색 범위를 1/2씩 줄여나가는 방식으로 작동하기 때문에 이진탐색이라고 부른다.

[이진 탐색 동작 방식]

1. 데이터 중앙에 있는 요소 고르기
2. 중앙 요소값과 찾는 목푯값을 비교
3. 목푯값이 중앙 요소값보다 작으면 왼편, 목푯값이 더 크면 오른편에서 이진 탐색 수행
4. 값을 찾을 때까지 위의 과정 반복

 

[이진 탐색 알고리즘 시간 복잡도 & 성능 분석]

이진 탐색은 탐색을 시도할 때마다 탐색 데이터 범위가 1/2로 줄어든다.

전체 데이터의 1/2, 1/4, 1/8, 1/16....

이렇게 데이터가 줄어들다가 내가 찾는 숫자가 미리 발견되면 즉시 종료되지만, 최악의 경우 탐색할 데이터가 1개가 되어야 종료된다.

 

데이터의 크기를 n, 탐색 반복 횟수를 x라고 하면, 탐색 데이터의 범위는 아래와 같다.

탐색 완료 시점에 데이터 범위가 1이라 하면,

이렇게 정리할 수 있다. 여기에 양변에 log₂ 를 취하면,

으로 정리할 수 있다.

 

따라서 이진 탐색의 최대 반복 횟수는 log₂n이다.

이진 탐색 시간 복잡도 : O(log₂n)

 

[이진 탐색 C언어 구현]

(모든 코드는 이미 배열의 데이터가 정렬되어 있어야지만 활용할 수 있다.)

[재귀 호출 방식]

int BinarySearch(int arr[], int left, int right, int target) {
    if (left > right) {  // 기저조건
        return -1;  // 탐색 실패
    }
    
    int mid = (left + right) / 2;  // 중간 인덱스 계산
    
    if (arr[mid] == target) {  // 타겟을 찾았을 때
        return mid;  // 인덱스 반환
    }
    else if (arr[mid] > target) {  // 중간 값보다 작을 때
        return BinarySearch(arr, left, mid - 1, target);  // 왼쪽 부분 배열에서 탐색
    }
    else {  // 중간 값보다 클 때
        return BinarySearch(arr, mid + 1, right, target);  // 오른쪽 부분 배열에서 탐색
    }
}

 

위와 같이 재귀 호출 방식으로 코드를 구현할 수 있다.

내가 타깃을 찾을 때까지 탐색 범위를 절반씩 줄여가면서 탐색 함수를 호출하는 것이다.

 

[반복문 방식]

int BinarySearch(int array[], int Size, int Target) {
	int left, right, mid;

	left = 0;
	right = Size - 1;

	while (left <= right) {
		mid = (left + right) / 2;

		if (Target == array[mid])
			return array[mid];
		else if (Target > array[mid])
			left = mid + 1;
		else
			right = mid - 1;
	}

	return -1;
}

 

위와 같이 반복문을 사용하여 right와 left 값을 조절해 가며 탐색 범위를 줄일 수도 있다.

 

---

[C언어 라이브러리 - 이진 탐색 함수 : bsearch()]

#include <stdlib.h>
void *bsearch(const void *key, const void *base,
              size_t num,
              size_t size,
              int (*compare)(const void *key, const void *element));

 

bsearch() 함수의 원형은 위와 같다.

 

• *key : 찾고자 하는 목푯값 데이터 주소 포인터
• *base : 데이터 배열의 주소 포인터
• num : 데이터의 크기, 요소의 개수
• size : 데이터 요소 하나의 크기
• (*compare) : 비교 함수 포인터

만약 함수에서 원하는 데이터 요소를 찾지 못하면 NULL을 반환한다.

원하는 요소를 찾은 경우에는 해당 데이터의 주소를 반환한다.

 

int Compare(const void* num1, const void* num2) {
	int* first = (int*)num1;
	int* second = (int*)num2;

	if (*first > * second)
		return 1;
	else if (*first < *second)
		return -1;
	else
		return 0;
}

 

위의 비교 함수를 작성하여 주면 bsearch() 함수가 잘 실행된다.

 

---

[이진탐색 활용 문제 : 백준 1920번]

이제는 이진 탐색을 활용한 문제를 풀어보자

 

1920번: 수 찾기

 

배열을 하나 입력받고, 다음에 숫자 M개를 입력받는다.

입력한 숫자가 배열 안에 있는 경우 1, 없는 경우 0을 출력하는 문제!

 

#include <stdio.h>
#include <stdlib.h>

int Compare(const void* num1, const void* num2) {
	int* first = (int*)num1;
	int* second = (int*)num2;

	if (*first > * second)
		return 1;
	else if (*first < *second)
		return -1;
	else
		return 0;
}

int main() {
	int N, M;
	scanf("%d", &N);

	int* arr1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
		scanf("%d", &arr1[i]);

	qsort(arr1, N, sizeof(int), Compare);

	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int num;
		scanf("%d", &num);

		int* p = NULL;
		p = bsearch((&num), arr1, N, sizeof(int), Compare);

		if (p == NULL)
			printf("0\n");
		else
			printf("1\n");
	}

	return 0;
}

 

기본적으로 이진 탐색은 데이터가 모두 정렬되어있어야 한다.

따라서 이전에 공부한 qsort() 함수를 이용하여 먼저 정렬해 주었다.

 

다음으로는 이제 찾아야 할 숫자들을 입력받는 동시에 bsearch() 함수를 활용하여 정답을 출력했다.

bsearch() 함수가 찾는 값이 없는 경우 NULL을 반환하기 때문에 NULL을 반환받은 경우엔 0을 아닌 경우에는 1을 출력하도록 만들어 주었다.

---

[이진 탐색 정리]

이진 탐색은 탐색해야 하는 데이터가 정렬된 상태에서만 사용할 수 있는 알고리즘이다.

데이터의 삽입, 삭제, 수정이 빈번한 데이터의 경우 매번 정렬하고 이진 탐색을 수행해야 한다는 단점이 있다.

 

그리고 이진 탐색은 C언어 라이브러리에 함수를 지원하고 있기 때문에 쉽게 호출하여 사용할 수도 있다.

---

컴퓨터 프로그래밍 전공하는 대학생이 공부했던 내용을 정리하기 위해 적는 소소한 블로그입니다.
잘못된 내용은 댓글에 달아주시면 피드백 감사히 받겠습니다!

[참고한 도서]
- 데이터 구조 원리와 응용
- 이것이 자료구조 + 알고리즘이다
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략