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

이진 탐색(Binary Search)이란?

우리가 종종 하는 업다운(Up & Down) 게임과 매우 유사한 검색 알고리즘이다. 리스트의 중간값을 선택해, 그 값이 목푯값인지, 아니면 앞에 있는지, 뒤에 있는지를 판단하고 목푯값을 찾을 때까지 이를 반복하는 알고리즘이다.

 

34를 검색하는 이진 탐색(Binary Search)

 

이진 탐색의 장 · 단점

• 매 탐색마다 범위의 절반을 덜어낼 수 있어 속도가 빠르고, 알고리즘의 구현도 비교적 간편하다.
• 다만, 특성상 정렬된 데이터에만 적용할 수 있기 때문에 정렬 작업이 선행되어야 한다.