1. 이분탐색(Binary Search)란 ?
이분탐색 = 이진탐색 이며, 정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 범위의 가운데 값을 검사하여 원하는 값이 나올 때까지 반씩 줄여나가며 찾는다.
2. 예시
1, 2, 3, 4, 5, 6이라는 값에서 6을 찾고자 한다면 배열의 중간에 위치한 3이라는 값과 6을 비교한다.
6은 3보다 크므로, 3의 왼쪽에 위치하는 값들은 찾을 필요가 없어 3의 오른쪽에 있는 값을 대상으로 탐색을 재시도한다.
이제 4, 5, 6이 남았고 그 중 가운데 값인 5와 6을 비교한다. 6은 5보다 크므로 5의 오른쪽 값을 대상으로 탐색을 재시도한다. 6과 6을 비교하면 값이 일치하므로 탐색을 종료한다.
3. 시간복잡도 문제
처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은 가장 나쁜 상황일 때 O(n)이라는 시간복잡성을 보여준다.
즉 10만개의 데이터가 있다면 10만번을 탐색해야한다는 것이다.
하지만 이 이분탐색(Binary Search)는 탐색 대상을 절반씩 계속 줄여나가기 때문에, 최악의 상황에서도 탐색 횟수가 log_2 n 이 되므로 10만개의 데이터가 있다하더라도 대략 16번정도로 탐색을 종료할 수 있다.
시간복잡도는 O(long n)이다.
4. 간단한 예제
프로그래머스 : 입국심사
1. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 2. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
Q. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 만들고, 그 시간을 구하라