코딩테스트 시간 초과 해결하는 이분탐색(Binary Search) 접근 순서와 설계 팁

코딩테스트 문제를 풀다 보면 분명히 정답인 것 같은데 '시간 초과'라는 네 글자 앞에 무너지는 경험, 다들 한 번쯤 있으시죠? 특히 데이터가 억 단위로 넘어가는 순간 우리가 믿을 건 선형 탐색이 아니라 이분탐색(Binary Search)뿐입니다.

 

처음 이 알고리즘을 접하면 이론은 참 쉽습니다. "중간 값 찍어서 크면 오른쪽, 작으면 왼쪽으로 가면 되는 거 아냐?"라고 생각하죠. 하지만 실제 시험장에서 "어디를 시작(left)과 끝(right)으로 잡아야 하지?" 혹은 "부등호에 등호를 넣어야 하나?" 같은 디테일에서 꼬이기 시작하면 30분은 우습게 날아갑니다. 2026년 현재 코테 트렌드에서도 이분탐색은 그 자체보다 '매개 변수 탐색'과 결합해 난이도를 높이는 주범으로 꼽히는데요. 제가 수많은 시행착오 끝에 정립한 '이분탐색 접근 루틴'을 공유해 드릴게요.

이분탐색을 써야 할 때? 데이터 규모에서 힌트 얻기

사실 이 알고리즘을 써야 할지 말지 결정하는 가장 명확한 기준은 입력값의 범위입니다. 보통 문제에서 배열의 크기가 10만 개 이상이거나, 찾아야 하는 값의 범위가 10억 단위를 넘어간다면 일단 의심부터 해야 합니다. 우리가 흔히 쓰는 루프(O(N))로는 도저히 1~2초 내에 해결할 수 없기 때문이죠.

 

예를 들어, 1부터 10억 사이의 숫자 중 하나를 맞히는 게임을 한다고 가정해 봅시다. 하나씩 물어보면 운이 없을 때 10억 번을 물어야 하지만, 이분탐색을 쓰면 단 30번 내외로 정답을 찾아냅니다. 이건 마치 두꺼운 백과사전에서 단어를 찾을 때 첫 장부터 넘기지 않고, 가운데를 툭 펼쳐서 앞뒤를 가늠하는 것과 같습니다.

실전에서 실패 없는 3단계 접근 가이드

이분탐색은 코드가 짧은 대신, 설계 단계에서 단 하나의 숫자만 틀려도 결과가 완전히 엇나갑니다. 제가 직접 문제를 풀며 검증한 가장 안전한 단계별 설계법입니다.

• Step 1: 무엇을 '정답'으로 두고 탐색할 것인가? - 가장 중요합니다. 나무 자르기 문제라면 '절단기 높이', 예산 문제라면 '배정된 예산'처럼 우리가 구하고자 하는 최종 결과값을 탐색의 대상으로 설정해야 합니다.
• Step 2: 탐색의 최소값(Left)과 최대값(Right) 확정하기 - 0부터 시작할지, 배열의 최소값부터 시작할지 명확히 해야 합니다. 최대값 역시 문제에서 주어진 물리적인 한계치(예: 20억)를 정확히 기입해야 무한 루프를 방지할 수 있습니다.
• Step 3: 결정 함수(Condition) 설계 - "이 중간값(Mid)으로 문제의 조건을 만족하는가?"를 판단하는 함수를 따로 분리하세요. "Yes"라면 정답 후보에 저장하고 범위를 좁혀나가는 식이죠.

직접 해보니 이 과정에서 결정 함수를 따로 만드는 습관이 실수를 줄이는 데 결정적이었습니다. 로직이 섞이면 mid 값을 업데이트할 때 멘탈이 흔들리거든요.

코딩테스트 이분탐색 - 생성형 ai 이미지

왜 내 이분탐색은 자꾸 무한 루프에 빠질까?

가장 많이 하는 실수가 바로 while문의 조건과 mid 업데이트 방식입니다. `left <= right`를 쓸지, 아니면 `left < right`를 쓸지에 따라 `mid + 1` 혹은 `mid` 처리가 달라지는데, 여기서 1 차이로 영원히 끝나지 않는 루프에 갇히게 됩니다.

 

2026년 최신 라이브러리 환경에서도 이 원리는 변하지 않습니다. 저는 보통 `while (left <= right)`를 기본형으로 잡고, 결과값을 찾을 때마다 `answer = mid`로 갱신해주는 방식을 선호합니다. 이 방식이 `left`를 출력할지 `right`를 출력할지 고민할 필요가 없어 훨씬 직관적이거든요. 난이도로 따지면 이 미세한 차이를 잡는 게 전체 구현의 80%를 차지한다고 해도 과언이 아닙니다.

상황별 이분탐색 vs 선형탐색 선택 기준

비교 항목	선형 탐색 (Sequential)	이분 탐색 (Binary)
데이터 조건	아무 조건 없음	반드시 정렬되어야 함
시간 복잡도	O(N)	O(log N)
권장 데이터 크기	1,000만 개 이하	1억 개 이상

표를 보면 데이터가 많아질수록 이분 탐색이 압도적으로 효율적입니다. 하지만 데이터가 적을 때는 정렬(Sorting)하는 데 걸리는 시간 때문에 오히려 선형 탐색이 빠를 수 있다는 점도 기억해야 합니다. 배보다 배꼽이 더 커지는 상황을 경계해야 하죠.

Q: 정렬되지 않은 배열에서도 이분탐색을 쓸 수 있나요?

A: 기본적으로는 불가능합니다. 하지만 '매개 변수 탐색'의 관점에서는 이야기가 다릅니다. 배열 자체가 아니라 우리가 찾는 '값의 범위'가 연속적(정렬된 상태)이라면, 그 범위를 쪼개면서 조건을 만족하는지 체크하는 방식으로 활용할 수 있습니다. 즉, 데이터가 아니라 '정답의 후보군'이 정렬되어 있다면 가능합니다.

이분탐색의 완성은 '매개 변수 탐색' (Parametric Search)

솔직히 말씀드리면, 요즘 기업 코딩테스트에서 단순 이분탐색은 거의 안 나옵니다. 대신 '최대값을 최소화하라' 혹은 '최소값을 최대화하라'는 식의 문제가 주를 이루죠.

 

이건 마치 뷔페에서 "배는 부르지만 본전은 뽑을 수 있는 최적의 접시 수"를 찾는 것과 비슷합니다. 접시 수가 늘어날수록 본전은 뽑히지만 배가 너무 부른 한계점, 그 경계를 이분탐색으로 빠르게 찾아가는 거죠. 직접 문제를 풀어보면 알겠지만, 일반적인 탐색 문제로 접근했다가 피를 본 후 이분탐색으로 전향했을 때의 그 짜릿함은 이루 말할 수 없습니다.

 

이분탐색은 화려한 기술보다 정교한 경계값 처리가 생명입니다. 시험장에 들어가기 전, 자신만의 `left`, `right` 업데이트 규칙을 머릿속에 박아두세요. "중간값이 정답이 될 수 있는가?"라는 질문에만 집중하면 의외로 술술 풀릴 겁니다. 단순히 코드를 외우기보다, 범위를 절반씩 날려버리는 그 속도감을 믿어보시길 바랍니다.

꽁꽁 얼린 냉동 삼겹살, 육즙 1도 안 빠지는 역대급 해동 비법