C++ 이진탐색 정리, 코드

이진 탐색 (Binary Search)

 

탐색 : 여러 개의 데이터 군집에서 특정 데이터를 찾는 일을 의미한다. 배열이 있을 때 가장 처음부터 끝까지 배열의 데이터를 확인하면서 탐색하는 것도 탐색의 예이다.(순차 탐색) 이진 탐색은 그 탐색 방법 중 하나이다. 이진탐색은 간단한 방식이지만 이 이진 탐색을 이용해 이진 트리 등 다양한 방면에서 사용된다.

 

• 이진 탐색의 조건

데이터들이 전부 정렬되어있어야 한다. (무작위일 때는 불가능)

또 기본적으로 중복된 데이터가 없을 시에 사용된다. 만약 중복된 데이터가 있으면 그 중 무작위로 아무거나 하나를 찾을 수 있닫고 생각하면 된다.

ex) 0 1 4 4 7 이 있을 때 4를 찾는다고 하면 세 번째 4를 찾을 수도 있고 네 번째 4를 찾을 수도 있다. 

 

• 이진 탐색의 알고리즘

이진 탐색은 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다는 특징이 있다.

 

해당 배열이 있을 때 그 배열의 시작점, 끝점, 중간점을 가지고 시작한다. 그리고 탐색하려는 데이터와 중간값을 비교한다.

 

1(start)

2

5(mid)

6

8(find)

9(end)

 

중간값과 찾으려는 값을 비교했을 때 해당 데이터가 중간값보다 크면 시작점을 중간점으로, 작으면 끝점을 중간점으로 옮기고 다시 중간값을 정하여 탐색한다. 이 과정을 반복하는 것이 이진탐색이다.

 

1

2

5

6(start)

8

9(find)

 

만약 시작점과 끝점이 같아지거나 엇갈리면 해당 데이터가 배열에 없는 것으로 하고 종료한다. 탐색 도중 해당 값을 찾으면 해당 값을 반환하고 종료한다.

이진 탐색의 알고리즘은 반씩 줄여나가기 때문에 따라서 O(logn)이라고 표현한다.

ex) 8개의 데이터가 있으면 3번 탐색만에 찾을 수 있다.

 

만약 크기 n의 배열이 있을 때 처음부터 하나씩 값을 대조해가며 탐색할 때 (순차 탐색 방법) 가장 최악의 시간복잡도로 O(n)이 나온다. (탐색하는 값이 맨 끝에 있거나 존재하지 않을 때)

하지만 이진 탐색의 경우는 시간복잡도가 O(logn)이기 때문에 더욱 효율적인 코드라고 할 수 있다. 반대로 순차 탐색은 정렬에 상관없이 값을 찾을 수 있으나 이진 탐색은 값이 정렬되어있어야 한다는 조건이 필요하다.

 

 

 

이진탐색 C++ 코드

 

재귀적으로 구현할 수도 있지만 반복문으로 구현하는 것이 구현도 쉽고 이해도 쉽다고 나는 생각한다. 일단 둘 다 구현해보았다.

 

• 반복문을 이용한 코드

 

int binary_search(int arr[], int find, int n)
{
	int start = 0, end = n - 1;

	while (start <= end) {
		int mid = (start + end) / 2;	// 소수점 버림
		//값이 존재할 때 인덱스 return
		if (arr[mid] == find)
			return mid;			
		else if(arr[mid] < find)
			start = mid + 1;
		else
			end = mid - 1;
	}

	return -1;				//값이 존재한다면 해당 값의 인덱스를, 아니면 -1을 return
}

 

• 재귀함수를 이용한 코드

 

int binary_search(int arr[],int find,int start, int end)
{
	if (start > end)
		return -1;					//존재하지 않음
        
	int mid = (start + end) / 2;	// 소수점 버림
	if (arr[mid] == find)
		return mid;
	else if (arr[mid] < find)
		return binary_search(arr, find, mid + 1, end);
	else
		return binary_search(arr, find, start, mid - 1);
}

 

 

• 실행 결과