이분 탐색(binary search)이란?

• 주어진 N개의 리스트 안에서 값을 탐색할 때 시간복잡도를 줄여주기 위해서 사용하는 방법
• N의 값이 클 때 빠른 탐색이 가능하다는 장점이 있다.
• 이분 탐색에서 중요한 것! Start와 End을 적절히 선정하여 반복을 통한 수렴하는 mid 값을 얼마나 잘 이용하는가에 달렸다.

이분 탐색을 사용할 시, 위와 같이 O(log N)의 속도로 구현이 가능하다.

구현할 때 미리 생각해보면 좋을 것들

• target : 찾고자 하는 값
• data : 오름차순으로 정렬된 list
• start : data 의 처음 값 인덱스
• end : data 의 마지막 값 인덱스
• mid : start, end 의 중간 인덱스

이분 탐색 사용 Methods

• While 문을 사용한 방식

백준 2110번 : 공유기 설치