[LeetCode-35] 이진 탐색 종료 조건은 left == right가 아니라 left > right다

• 문제 링크: https://leetcode.com/problems/search-insert-position/
• 파일 경로: src/main/java/coding_test/이진탐색/LC0035_SearchInsertPosition.java
• 난이도: Easy

문제 설명

정렬된 서로 다른 정수 배열 nums와 target이 주어진다. target이 배열에 있으면 인덱스를, 없으면 정렬 순서를 유지하며 삽입될 위치를 반환한다.

Input: nums = [1,3,5,6], target = 5   -> Output: 2
Input: nums = [1,3,5,6], target = 2   -> Output: 1
Input: nums = [1,3,5,6], target = 7   -> Output: 4

시행착오

704 템플릿을 그대로 가져와서 짜고, 루프 밖에서 뭘 반환할지가 문제였다. 첫 시도:

return mid + 1;

target = 7(모든 값보다 큼)에서는 우연히 맞았지만, target = 0(모든 값보다 작음)으로 테스트하니 1이 나왔다. 정답은 0이어야 하는데.

원인을 찾다가 “루프가 언제 끝나는가”부터 잘못 알고 있었다는 걸 깨달았다. 처음엔 left == right일 때 끝난다고 생각했는데, 실제 루프 조건은 while (left <= right)라 left > right가 됐을 때 끝난다. target = 0 케이스를 손으로 추적해보면 right가 계속 줄어들면서 left는 그대로 0에 머무는데, mid + 1은 마지막 mid(0) + 1 = 1을 반환해서 틀린 것이었다.

최종 코드

public static int solution(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int mid = 0;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

변수 추적표 (target = 7, 못 찾는 케이스)

nums = [1, 3, 5, 6]

반복	left(시작)	right(시작)	mid	nums[mid]	비교	갱신
1	0	3	0+(3-0)/2=1	3	3 < 7	left = 2
2	2	3	2+(3-2)/2=2	5	5 < 7	left = 3
3	3	3	3+(3-3)/2=3	6	6 < 7	left = 4
—	4	3	left(4) <= right(3)? 거짓 → 종료

루프 종료 시 left = 4, right = 3 → return left = 4 (정답)

오늘 배운 내용

이 문제에서 가장 중요한 한 가지는, 루프가 끝나는 정확한 시점이다.

루프가 끝나는 순간(left > right), left가 정확히 삽입 위치를 가리킨다.

nums[mid] < target이었던 마지막 갱신은 left = mid+1이 되고, nums[mid] > target이었던 마지막 갱신은 right = mid-1이 되는데 — 두 경우 모두 left가 최종적으로 “target보다 큰 첫 원소의 위치”를 가리키게 된다. 즉 종료 조건과 반환값은 세트로 외워야 한다: left <= right로 도는 이진 탐색은 종료 후 left가 답이 되는 경우가 많다.

오답노트

• 틀렸던 생각: “루프는 left == right일 때 끝난다”고 착각했다. 실제 종료 조건은 루프 조건(left <= right)의 부정, 즉 left > right다.
• 왜 이 착각이 위험한가: left == right를 기준으로 생각하면, 답이 배열의 양 끝을 벗어나는 케이스(모든 원소보다 작거나 큰 target)에서 left와 right가 아예 교차해버리는 상황을 놓치게 된다. 이번 문제처럼 target = 0인 경우 right는 -1까지 내려가고 left는 0에 머무는데, “언젠가 둘이 같아지겠지”라고 생각하면 이 케이스를 이해할 수 없다.
• 고친 인식: 루프 조건이 while (A)이면, 루프는 항상 !A가 될 때 끝난다. A가 left <= right니까 종료는 left > right. 이 관계를 조건문 그대로 뒤집어서 확인하는 습관을 들였다.
• 언제 다시 떠올릴까: 이진 탐색에서 “종료 후 반환값이 뭐가 되어야 하나” 헷갈릴 때마다, 루프 조건을 먼저 문자 그대로 뒤집어서 종료 조건부터 확인한다.

꿀팁

• 이 문제는 일종의 “lower bound(하한) 이진 탐색”의 기본형이다 — “target 이상인 첫 위치를 찾아라” 같은 문제를 만나면 이 패턴(left <= right, 종료 후 left 반환)을 그대로 재사용할 수 있다.
• 헷갈릴 때는 극단적인 입력(배열의 모든 원소보다 크거나 작은 target)을 손으로 직접 추적해보는 게 종료 조건을 이해하는 데 제일 효과적이었다.