Krafton Jungle/2. Keywords

[WEEK02] 이진 탐색

munsik22 2025. 3. 20. 15:50

이진 탐색 (또는 이분 탐색, 이진 검색, Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다. 이진 탐색은 배열의 중간 값을 기준으로 찾고자 하는 값과 비교하며 탐색 범위를 절반씩 줄여나간다. 따라서 시간 복잡도는 O(log n)으로 매우 빠른 탐색 속도를 제공한다.

이진 탐색의 특징

  • 배열이 정렬되어 있어야 한다: 정렬되지 않은 경우 먼저 정렬 후 사용
  • 빠른 탐색이 필요할 때 유용하다: (예) 데이터베이스 검색, 사전 검색 등

이진 탐색의 동작 원리

  1. 배열의 중앙값을 선택한다 (center)
  2. 중앙값이 찾고자 하는 값과 같다면 탐색 종료
  3. 찾는 값이 중앙값보다 작다면 왼쪽 절반을 탐색
  4. 찾는 값이 중앙값보다 크다면 오른쪽 절반을 탐색
  5. 위 과정을 값이 발견되거나 탐색 범위가 없을 때까지 반복한다

코드 구현

(1) 반복문을 사용한 이진 탐색

def bin_search(arr, key):
	pl = 0
    pr = len(arr) - 1
    
    while True:
    	center = (pl + pr) // 2
        if arr[center] == key:
        	return center
        elif arr[center] < key:
        	pl = center + 1
        else:
        	pr = center - 1
        if pl > pr:
        	break
        return -1 # 검색 실패
 
 n = int(input())
 arr = list(map(int, input().split()))
 arr.sort()
 
 key = int(input())
 print(bin_search(x, key))

(2) 재귀함수를 사용한 이진 탐색

def bin_search(arr, key, pl, pr):
    if pl > pr:
        return -1  # 검색 실패

    center = (pl + pr) // 2
    if arr[center] == key:
        return center
    elif arr[center] < key:
        return bin_search(arr, key, center + 1, pr)
    else:
        return bin_search(arr, key, pl, center - 1)

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

key = int(input())
print(bin_search(arr, key, 0, n-1))

이진 탐색의 시간 복잡도 분석

  • 최선의 경우 : O(1) ← 배열의 중앙값이 처음부터 찾고자 하는 값과 같은 경우
  • 최악의 경우 : O(log n) ←  배열을 계속 반으로 나누면서 탐색하는 경우
  • 평균적으로 : O(log n) ← 대부분의 경우 절반씩 탐색 범위를 줄여가므로 로그 시간에 수렴

사용 예시

(1) 정렬된 배열에서 첫 번째 또는 마지막 위치 찾기

def find_first_and_last(nums, target):
    def binary_search_first():
        left, right = 0, len(nums) - 1
        first = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                if nums[mid] == target:
                    first = mid
                right = mid - 1
            else:
                left = mid + 1
        return first

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

    return [binary_search_first(), binary_search_last()]

# 테스트 예제
nums = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(find_first_and_last(nums, target))  # 출력: [1, 3]

(2) 제곱근 구하기 (정수 부분만)

def sqrt_integer(x):
    if x == 0 or x == 1:
        return x
    
    left, right = 0, x
    ans = 0
    
    while left <= right:
        mid = (left + right) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
            
    return ans

# 테스트 예제
print(sqrt_integer(8))  # 출력: 2
print(sqrt_integer(16)) # 출력: 4

(3) 나무 자르기 문제 (최대 높이 찾기)

def tree_cutting(heights, M):
    left, right = 0, max(heights)
    result = 0

    while left <= right:
        mid = (left + right) // 2
        total = sum(h - mid for h in heights if h > mid)

        if total >= M:
            result = mid  # 최대 높이 갱신
            left = mid + 1
        else:
            right = mid - 1

    return result

# 테스트 예제
tree_heights = [20, 15, 10, 17]
M = 7
print(tree_cutting(tree_heights, M))  # 출력: 15

(4) 배열에서 특정 원소의 삽입 위치 찾기 

def lower_bound(nums, target): # 타겟 값 이상이 처음 등장하는 위치
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(nums, target): # 타겟 값 초과가 처음 등장하는 위치
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# 테스트 예제
nums = [1, 2, 4, 4, 5, 6]
target = 4
print(lower_bound(nums, target))  # 출력: 2
print(upper_bound(nums, target))  # 출력: 4

(5) 두 배열에서 공통 원소 찾기

def find_common_elements(arr1, arr2):
    result = []
    left, right = 0, 0

    while left < len(arr1) and right < len(arr2):
        if arr1[left] == arr2[right]:
            result.append(arr1[left])
            left += 1
            right += 1
        elif arr1[left] < arr2[right]:
            left += 1
        else:
            right += 1

    return result

# 테스트 예제
arr1 = [1, 2, 4, 6, 8]
arr2 = [2, 4, 6, 10]
print(find_common_elements(arr1, arr2))  # 출력: [2, 4, 6]

(6) 가장 가까운 숫자 찾기 

def closest_number(nums, target):
    left, right = 0, len(nums) - 1
    best = nums[0]

    while left <= right:
        mid = (left + right) // 2
        if abs(nums[mid] - target) < abs(best - target):
            best = nums[mid]
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return nums[mid]

    return best

# 테스트 예제
nums = [1, 3, 5, 7, 9]
target = 6
print(closest_number(nums, target))  # 출력: 5

(7) 피크 원소 찾기

def find_peak_element(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1

    return nums[left]

# 테스트 예제
nums = [1, 3, 7, 8, 6, 4, 2]
print(find_peak_element(nums))  # 출력: 8 (또는 7)

(8) 최소의 k번째 원소 찾기 (두 배열을 합쳤을 때 k번째 작은 수)

from bisect import bisect_right

def kth_smallest(arr1, arr2, k):
    left, right = min(arr1[0], arr2[0]), max(arr1[-1], arr2[-1])

    def count_less_or_equal(x):
        return sum(bisect_right(arr, x) for arr in [arr1, arr2])

    while left < right:
        mid = (left + right) // 2
        if count_less_or_equal(mid) < k:
            left = mid + 1
        else:
            right = mid

    return left

# 테스트 예제
arr1 = [2, 3, 6, 7, 9]
arr2 = [1, 4, 8, 10]
k = 5
print(kth_smallest(arr1, arr2, k))  # 출력: 4

(9) 최소 작업 시간 찾기 (공장 기계 문제) 

def min_time(machines, N):
    left, right = 1, max(machines) * N

    def count_jobs(time):
        return sum(time // m for m in machines)

    while left < right:
        mid = (left + right) // 2
        if count_jobs(mid) >= N:
            right = mid
        else:
            left = mid + 1

    return left

# 테스트 예제
machines = [2, 3, 7]
N = 10
print(min_time(machines, N))  # 출력: 최소 시간

bisect 모듈

이진 탐색을 기반으로 한 리스트 삽입 및 검색 기능을 제공하는 표준 라이브러리다. 직접 이진 탐색을 구현할 필요 없이 간편하게 사용할 수 있다.

  • bisect.bisect_left(arr, x) : x를 삽입할 왼쪽 위치
  • bisect.bisect_right(arr, x) : x를 삽입할 오른쪽 위치
  • bisect.insort_left(arr, x) : x를 왼쪽 기준 삽입
  • bisect.insort_right(arr, x) : x를 오른쪽 기준 삽입

bisect vs list.index()

기능 bisect list.index()
정렬된 리스트에서 빠르게 찾기 ✅ 빠름 (O(logN)) ❌ 느림 (O(N))
중복 원소 처리 ✅ 가능 ❌ 첫 번째 원소만 찾음
새로운 값 삽입 ✅ 정렬된 상태 유지 ❌ 직접 삽입 필요

정리

이진 탐색은 정렬된 배열에서 매우 빠른 검색을 가능하게 하는 효율적인 알고리즘이다. 반복문과 재귀를 사용하여 구현할 수 있으며, O(log n)의 시간 복잡도를 가지므로 데이터가 많아질수록 유용성이 증가한다. 정렬된 데이터에서 검색을 최적화하려면 이진 탐색을 적극 활용하자. 🚀

'Krafton Jungle > 2. Keywords' 카테고리의 다른 글

[WEEK02] 원형 큐, 우선순위 큐  (0) 2025.03.22
[WEEK02] 스택/큐, 데크  (0) 2025.03.21
[WEEK01] 완전 탐색  (0) 2025.03.18
[WEEK01] 복잡도와 정렬  (0) 2025.03.16
[WEEK01] 정수론  (0) 2025.03.15

'Krafton Jungle/2. Keywords'의 다른글

  • 현재글[WEEK02] 이진 탐색

관련글

티스토리툴바