[C++/알고리즘] 이진탐색

 

이진 탐색 알고리즘은 '정렬된 상태의 배열' 에서 원하는 값을 O(log n) 만에 탐색할 수 있는 알고리즘 입니다.

그 방법은 '업앤다운 숫자맞추기'를 하는 방법과 유사합니다.

 

1~50 중에서 상대방이 생각한 숫자를 가장 빨리 맞추는 방법은

절반인 25를 말해서 업, 다운을 듣고

 

업! 이라면 37

다운! 이라면 12

을 말하면서 점차 줄여나가는 방식입니다.

 

계속 절반 절반 반띵하면서 원하는 수를 찾아가는 것이죠.

 

 

샘플코드 입니다.

 

찾고자 하는 값이

mid 값보다 크냐 작냐에 따라서

찾고자하는 범위를 좁혀나가는 것입니다.

 

 

재귀적으로 코드를 구성할 수 있습니다.

 

 

이진탐색의 경우 log2 N 의 시간복잡도를 가지며,

임의 접근이 불가한 연결리스트의 경우에는 설사 정렬이 되어 있더라도 이진 탐색을 사용할 수 없습니다.