이진 탐색

 

이진 탐색이란?

 

 

이진 탐색 (Binary search)

---

이진 탐색은 정렬 된 데이터 배열에 특정 값을 찾아내는 알고리즘이다.

중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교 후 X가 중간값보다 작으면 중간값 기준 좌측, X가 중간값 기준으로 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하여 비교한다. 

해당 값을 찾을때까지 이 과정을 반복한다.

 

 

 

 

위 그림을 보면 오름차순으로 정렬된 배열에서 Target(22)를 찾는 이진 탐색을 시작한다. 탐색을 반복적으로 수행하여 마지막 22 타겟을 찾는다.

 

시간복잡도 : O(logN)

 

해당 알고리즘은 반복문과 재귀 두가지 방법으로 구현이 가능하다.