[Algorithm] 이분탐색, Binary Search

[프로그래머스 > 코딩테스트 연습 > 이분탐색　> 입국심사] 문제에 활용됨

이분탐색 (Binary Search)

• 다양한 탐색 기법중 하나로 탐색 범위를 절반으로 줄여가며 찾아가는 탐색방법임
• 순차탐색처럼 전부 탐색하는 것이 아니라서 비교적 탐색 속도가 빠름
• 특징으로는 left, right, mid 값을 활용하여 탐색한다는 점이 있음

 

이분탐색 조건

• 이분 탐색을 하고자하는 대상(배열)은 정렬되어있어야 함

 

알고리즘 순서

1. left, right를 설정해준다.
2. mid를 left와 right의 중간으로 설정한다.
3. mid와 찾고자 하는 값과의 대소 관계에 따라 left 혹은 right 값을 조정해준다.
   • mid < 찾고자하는 값 이면 left 를 mid+1로 설정한다.
   • mid > 찾고자하는 값 이면 right 를 mid-1로 설정한다.
4. 2~3 순서를 반복하여 찾고자 하는 값이 나올 때까지 반복한다.

그림으로 설명

 

이분탐색 시간복잡도

• 순차탐색에서 시간복잡도가 O(n)이라면 이분탐색에서는 범위를 절반씩 줄여가며 탐색하기 때문에 시간복잡도가 O(log(n))이 된다고 한다.
• 확실히 개수가 많을 때 계산량을 확연히 줄여주기 때문에 코딩테스트에서 잘 활용되고 있다.