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

이미 정렬된 배열 or 리스트에 대해 특정 원소가  포함되어 있는지 판단하는 알고리즘.

 

전체 범위에서  중심 값을 이용해 판단 기준을 체크함.

 

ex)

 

오름차순 정렬일때

 

해당값이 중심값보다 크면 중심값 왼쪽은 무시.

 

            중심값보다 작으면 오른쪽 무시.

 

범위 줄임.

 

줄인 범위의 중심값.

 

다시 조건 검색으로

 

원소 있으면 true

없으면 false

 

 

이미 정렬이 된 배열에 대해서는 O(logN)

정렬이 안된 배열에 대해서는 O(NlongN) 이 필요.