이진 탐색(Binary Search)

 이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 효율적으로 찾는 알고리즘입니다. 배열의 중간 요소와 목표 값을 비교하여, 목표 값이 더 작으면 왼쪽 절반, 더 크면 오른쪽 절반을 선택하여 검색을 반복합니다. 최악의 경우 시간 복잡도는 O(log⁡n)입니다.

---

「이진 탐색의 동작 과정」

---

1. 분할 과정 (Divide)

우선 알아야할점은 배열은 항상 정렬 되어있어야 한다는 것입니다. 첫번째 분할과정에서는 현재 배열의 중간 원소를 선택합니다. 그 후 중간 원소와 찾고자 하는 값을 비교합니다.

-IF 찾고자 하는 값이 중간 요소보다 작으면 : 배열에서 중간 원소의 왼쪽 절반을 선택합니다.

-IF 찾고자 하는 값이 중간 요소보다 크면 : 배열에서 중간 원소의 오른쪽 절반을 선택합니다.

1

2

3

4

5

 

위 배열에서 2를 찾아야 할때, 2는 중간원소 3보다 작음으로

1

2

 

의 구간을 선택한다.

---

2. 정복 과정 (Conquer)

  두번째 과정인 정복과정에서는 선택된 절반에 대해 이진 탐색을 재귀적으로 수행합니다. 이 과정에서 배열의 크기는 계속 절반으로 줄어들며, 중간 요소와 비교를 반복합니다.

1

2

위 배열에서 중간원소 1보다 찾아야하는 2가 더 큼으로

2

의 구간을 선택한다.

중간원소 2가 찾아야하는 원소 2와 같음으로 2의 idx값을 찾았다.

---

3. 결합 과정 (Combine)

재귀적 탐색 과정을 통해 중간 요소가 찾고자 하는 값과 일치하면 값을 찾은 것이고, 더 이상 분할할 배열이 없으면 찾지 못한 것입니다. 이진 탐색은 값을 찾을 때까지 또는 배열이 비워질 때까지 재귀적으로 반복하므로 별도의 병합 과정이 필요 없습니다.

---

이진 탐색을 공부했으니 다음 문제를 풀어보자

https://www.acmicpc.net/problem/1920

《소스코드》

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int arr[100010];
int m;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	sort(arr, arr + n);
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		int low = 0, che = 0, high = n - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] == x) {
				printf("1\n");
				che = 1;
				break;
			}
			else if (arr[mid] < x) low = mid + 1;
			else high = mid - 1;
		}
		if(che == 0) printf("0\n");
	}
	return 0;
}