[알고리즘] 이진 탐색(Binary Search)

 

 

 

 

 

알고리즘 개요 및 소개

7을 찾는 이진탐색의 시각화

이진 검색 알고리즘(Binary Search Algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

검색 원리상 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때 마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

시간 복잡도	O(logN)
장점	원하는 값을 찾고자할 때 빠르게 찾을 수 있다.
단점	정렬이 된 데이터에서만 탐색이 가능하다.

소스코드

#include<iostream>
constexpr int MAX = 15;
int data = 12;
void Binary_Search(int* list,int min,int max) {

	int mid = (min + max) / 2;

	if (list[mid] == data) { std::cout << "find Data: " << list[mid]<<"in: "<<mid; return; }

	else if (list[mid] < data)
		Binary_Search(list, mid + 1, max);
	else
		Binary_Search(list, min, mid-1);

}

int main() {
	int list[MAX]{ 1,2,3,4,5,6,6,7,7,8,9,10,11,12,13};
	Binary_Search(list, 0, MAX);
}

재귀 함수를 이용하여 구현한 이진 검색(Binary Search)

 

후기

탐색 알고리즘 중 하나인 이진 탐색을 재귀함수를 이용하여 구현하였다. 여러 곳에서 응용이 되는 알고리즘인 만큼 숙지가 필수이다.

 

 

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/이진_검색_알고리즘