호접몽

이분 탐색이란?

순차탐색처럼 처음부터 끝까지 모든 데이터를 확인하여 찾는 것이 아니라
정렬되어 있는 데이터를 대상으로 탐색범위를 절반씩 줄여가며 찾아가는 탐색 방법.

이분 탐색의 전제 조건은 정렬되어 있는 데이터를 대상으로 한다는 것.

탐색 과정

1 2 3 4 5 6 이라는 값에서 4를 찾는다면
배열의 중간에 위치한 3을 골라 4와 비교하여
찾아야하는 값인 4가 3보다 크므로
3보다 왼쪽에 위치한 값은 탐색하지 않고
3보다 큰 값들인 오른쪽에 위치한 값들의 대상으로 다시 탐색 시도

3보다 큰 값인 4부터 6중 다시 중간값 5와 비교하여 4는
5보다 작으므로 5의 왼쪽 값들을 대상으로 탐색 시도
5의 왼쪽값은 4밖에 없으므로 4와 4를 비교하여 일치하므로 탐색 종료

만약 해당 자리에 4가 아닌 다른 값이 있었다면 탐색종료
그 외 값을 찾지 못할 때 탐색 종료는 인덱스를 판단해서 결정

예제 그림

효율성

처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은

Worst Case일 때 O(n)의  시간 복잡도를 보여줌.
10만개의 데이터가 있다면 10만번 탐색 시도.

그러나, 이분 탐색은 탐색 대상을 절반씩 계속해서 줄여나가기 때문에

Worst Case일 때 O(log N) 이 됨.
10만개의 데이터가 있다고 하더라도 약 16번 정도로 탐색을 끝낼 수 있음. 

Best Case는 중간값이 탐색 대상일때니까 O(1).

관련 문제

https://www.acmicpc.net/problem/1920
https://www.acmicpc.net/problem/1654
https://www.acmicpc.net/problem/1300
https://www.acmicpc.net/problem/10816

참고 사이트

https://satisfactoryplace.tistory.com/39
https://wootool.tistory.com/62

추천 사이트

https://anster.tistory.com/152
https://blockdmask.tistory.com/167