sorted-inputsearch-spacelogarithmic-time

Binary Search를 설명해 주세요

예상 시간
5분
30초 답변

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

Binary Search의 전제 조건은 무엇인가요?

부가 설명

전화번호부에서 이름을 찾을 때 처음부터 한 장씩 넘기지 않는 것과 비슷합니다. 가운데를 보고 찾는 값이 앞쪽에 있을지 뒤쪽에 있을지 판단한 뒤, 가능성이 없는 절반은 버립니다. 이 “버릴 수 있는 근거”가 정렬입니다.

Binary Search는 단순 탐색뿐 아니라 답의 범위를 줄이는 문제에도 쓰입니다. 예를 들어 최소 가능한 시간, 최대 가능한 길이처럼 조건을 만족하는 경계값을 찾을 때도 사용할 수 있습니다. 이때는 mid가 정답인지보다 조건을 만족하면 어느 방향을 버릴 수 있는지가 더 중요합니다.

한 줄 정리

Binary Search는 정렬 또는 단조성을 근거로 답이 없는 절반을 계속 버리는 알고리즘입니다.