704. 이진 탐색 기본

정렬된 배열에서 특정 값을 찾을 때 이진 탐색을 사용할 수 있습니다. 중앙값을 기준으로 탐색 범위를 절반씩 줄여나가는 방식입니다.

class BinarySearch:
    def find_index(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

35. 삽입 위치 찾기

값이 존재하지 않을 때 삽입 위치를 반환하는 문제입니다. 탐색 종료 후 left 변수가 삽입 지점을 가리킵니다.

class InsertPosition:
    def find_insert_index(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

34. 시작 및 종료 위치 찾기

정렬된 배열에서 특정 값의 첫 번째와 마지막 위치를 찾는 문제입니다. 두 번의 이진 탐색을 통해 각각의 경계를 찾을 수 있습니다.

class RangeFinder:
    def find_boundaries(self, nums, target):
        def find_left():
            left, right = 0, len(nums) - 1
            result = -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    right = mid - 1
                    result = mid
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result

        def find_right():
            left, right = 0, len(nums) - 1
            result = -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    left = mid + 1
                    result = mid
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result

        return [find_left(), find_right()]

69. 제곱근 계산

주어진 정수의 제곱근을 정수 형태로 반환하는 문제입니다. 이진 탐색을 통해 효율적으로 계산할 수 있습니다.

class SquareRoot:
    def calculate(self, x):
        left, right = 0, x
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            if square == x:
                return mid
            elif square < x:
                left = mid + 1
            else:
                right = mid - 1
        return right

367. 완전 제곱수 확인

주어진 수가 완전 제곱수인지 판단하는 문제입니다. 이진 탐색으로 제곱값을 비교해 나가며 판단합니다.

class PerfectSquareChecker:
    def is_perfect_square(self, num):
        left, right = 0, num
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            if square == num:
                return True
            elif square < num:
                left = mid + 1
            else:
                right = mid - 1
        return False

요약 및 정리

이진 탐색은 정렬된 배열에서 특정 값을 찾거나 경계값을 결정하는 데 매우 유용합니다. 탐색 범위의 갱신 방식, 반복 조건, 종료 후 상태를 정확히 이해하면 다양한 변형 문제를 해결할 수 있습니다.