BST: 704. Binary Search

704. Binary Search

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bst(l, r):
            while l<=r:
                mid = (l+r)//2
                if nums[mid] < target:
                    l = mid+1
                elif nums[mid] > target:
                    r =mid -1
                else:
                    return mid

            return -1

        return bst(0, len(nums)-1)

 

https://youtu.be/s4DPM8ct1pI?si=E2bD8-D_rcUUtBXz

 

 

최종 코드

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1

        while l<=r:
            m = (l+r)//2
            if nums[m] < target:
                # l+=1
                l = m+1
            elif nums[m] > target:
                # r-=1
                r = m-1
            else:
                return m
        # print(l, r)
        return -1

 

while l <= r: vs while l < r: 는 binary search(이진 탐색)에서 루프의 종료 조건에 따라 달라짐

각각의 차이를 쉽게 이해할 수 있게 아래에 정리해드릴게요.

---

✅ while l <= r:

• 가장 일반적인 형태
• l과 r이 같은 위치일 때도 탐색을 수행함
• 모든 인덱스를 포함해서 검사할 수 있음
• ✔️ 타겟의 인덱스를 찾을 때 주로 사용

예시:

while l <= r:
    m = (l + r) // 2
    if nums[m] < target:
        l = m + 1
    elif nums[m] > target:
        r = m - 1
    else:
        return m

이렇게 하면 l == r일 때도 마지막으로 한 번 비교하게 되어, 인덱스를 정확히 찾을 수 있어요.

---

✅ while l < r:

• 범위를 좁혀가는 탐색 (예: 첫 번째 만족하는 위치, 최소값 찾기 등)
• l == r이 되는 순간은 이미 찾았다고 가정
• 종료 후 l이나 r이 정답 후보가 됨
• ✔️ lower bound, upper bound 같은 위치 계산할 때 사용

예시 (lower bound 찾기):

while l < r:
    m = (l + r) // 2
    if nums[m] < target:
        l = m + 1
    else:
        r = m

이렇게 하면 target 이상(>= target)이 처음 나오는 위치를 찾을 수 있어요.

---

🔍 핵심 차이 요약

조건	의미	사용 예
l <= r	마지막 원소까지 탐색	정확한 값(인덱스) 찾기
l < r	최소/최대 조건 위치 탐색	lower bound, upper bound, 조건 만족 위치