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

 이진 탐색 알고리즘은 검색 범위를 줄여 나가면서 원하는 데이터를 검색할 때 사용하는 알고리즘이다.

 

 오름차순으로 정렬된 리스트를 반으로 나누고 찾는 원소가 중간에 있는지 확인하고, 없으면 위쪽 또는 아래쪽에 있는지를 판단하여 다시 같은 방식으로 원소를 찾는 방법이다.

 

 게임 'up & down'을 예로 들면, 1부터 100까지의 수 중에서 41이라는 숫자를 찾는다고 한다. 먼저 중간 값인 50이나 51중에서 찾으려는 41이 두 값보다 작기 때문에 1부터 49를 새로운 범위로 설정해서 찾는다. 다시 절반인 25를 기준으로 찾으려는 41이 크기 때문에 26부터 49까지 새로운 범위로 설정해서 찾는다.

 

 이렇게 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 방법을 이진 탐색 알고리즘이라고 한다.

 

 

 

 

사용

 주로 대규모의 데이터를 검색하는 데 사용한다.

 

 정렬된 배열에서 요소값을 더 효율적으로 검색하거나 데이터의 양이 많을 때 사용한다. 데이터의 양이 많을수록 더 효율이 좋다.

 

 예를 들면, 사전에서 단어를 찾을 때나 도서관에서 도서를 검색할 때 또는 대규모 시스템에 대한 리소스 사항을 파악할 때 등이 있다.

 

 

 

 

한계

 

• 배열에만 구현할 수 있다.
  
  
• 정렬되어 있지 않다면 효율이 높지 않기 때문에 정렬되어 있는 상태에서 구현한다.