Technical Interview Master Plan [5] - Binary Search는 아는데 왜 경계값 문제에서 자꾸 틀리는가

이진탐색 Binary Search 의 개념 그리고 문제 해결 전략을 배워봅니다.

Introduction to Binary Search

먼저 이진 탐색의 개념을 다루어보면, 표준 영어 사전이 있고 우리가 ‘Internet’ 이라는 단어 정의를 찾고 싶다고 가정해보자.

우리는 어떻게 해야 할까? 한 가지 방법은 처음부터 끝까지 한 페이지씩 넘기며 ‘internet’ 이 나오는 페이지에 도달할 때까지 찾는 것이다. 그러나 이 방법은 비효율적이며, 현실적으로는 사전의 중간 쯤 되는 페이지를 먼저 펼칠 가능성이 더 크다.

예를 들어, 중간을 펼쳤는데 ‘M’ 으로 시작하는 단어들이 있는 페이지라고 해 보자. ‘internet’은 알파벳 순서상 ‘M’ 보다 왼쪽에 있으므로, 우리는 ‘A’ 와 ‘M’ 사이 어딘가의 페이지를 펼치게 된다. 그리고 현재 페이지를 기준으로 ‘internet’이 왼쪽에 있는지 오른쪽에 있는지를 확인하는 과정을 반복하면서 탐색 범위를 점점 좁혀 나간다. 결국 원하는 페이지를 찾게 된다. 이 방법을 사용하면 모든 페이지를 순차적으로 넘기는 것과 달리, 검색 해야할 페이지 수를 크게 줄일 수 있다. 이것이 이진 탐색의 기본 개념이다.

이제 구현부를 알아본다. 이진 탐색은 정렬된 데이터 집합에서 값을 찾는 알고리즘이다. 숙련된 개발자들조차 정확한 구현이 까다롭다고 느끼는데, 세부 조건이 매우 중요하기 때문이다. left 와 right를 어떻게 초기화할지, while 반복문의 종료 조건을 left < right 로 할지 left <= right 로 할지, 그리고 경계를 left = mid, left = mid + 1, right = mid, right = mid - 1 중에서 무엇으로 갱신할 지 결정해야 한다.