[알고리즘] 이진탐색

 

이진탐색이란?

이진탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾거나, 그 값이 위치할 수 있는 인덱스를 찾는 데 매우 효율적인 알고리즘이다.

즉, 최적의 값이나 인덱스의 위치를 찾는데 유용하다.

---

이진탐색의 종류

 

1. 값이 삽입될 인덱스를 이진탐색하는 경우
목적: 특정 값이 위치할 수 있는 배열의 인덱스를 찾는 것.
방법: 배열에서 중간 인덱스를 선택하고, 찾고자 하는 값과 중간 인덱스의 값을 비교한다. 찾고자 하는 값이 중간 인덱스 값보다 작다면, 배열의 왼쪽 절반을 검색하고, 크다면 오른쪽 절반을 검색한다. 이 과정을 반복하여 값을 찾거나, 값을 찾지 못하는 경우 해당 값이 위치할 수 있는 인덱스를 반환한다.

def binary_search_index(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    # target이 존재하지 않는 경우, 삽입될 위치의 인덱스 반환
    return left

# 예시 사용
arr = [1, 3, 5, 7, 9]
print(binary_search_index(arr, 6))  # 출력: 3 (6이 들어갈 위치)

---

2. 배열의 값으로 이진 탐색을 사용하는 경우

이진 탐색은 일반적으로 정렬된 배열에서 특정 값을 효율적으로 찾기 위해 사용된다. 하지만, 배열의 값으로 이진 탐색을 사용하는 경우는 최적화 문제를 해결할 때도 많이 사용된다. 이러한 경우, 이진 탐색을 통해 특정 조건을 만족하는 최대/최소 값을 찾는 방식이다.

배열의 값으로 이진 탐색을 사용하는 일반적인 경우는 다음과 같다.

1. 최적화 문제:
   • 특정 조건을 만족하는 최대/최소 값을 찾고자 할 때, 이진 탐색을 사용하여 탐색 범위를 줄여나가는 방식이다. 예를 들어, 가장 인접한 두 공유기 사이의 최대 거리를 찾는 문제에서는 가능한 거리 값을 이진 탐색으로 줄여가며 조건을 만족하는 최대 거리를 찾는다.
2. 결정 문제:
   • 답이 '예' 또는 '아니오'로 결정되는 문제에서, 특정 조건을 만족하는 가장 큰 값 또는 작은 값을 찾는 경우이다. 예를 들어, 특정 거리로 공유기를 설치할 수 있는지 확인하는 문제에서, 이 거리를 이진 탐색으로 줄여가며 가능한 최대 거리를 찾는다.

def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]

        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

---

백준 문제

https://www.acmicpc.net/problem/1654

https://www.acmicpc.net/problem/2512

https://www.acmicpc.net/problem/1939

https://www.acmicpc.net/problem/2110

 

---

문제 예시 (2. 배열의 값으로 이진 탐색을 사용하는 경우)

2-1. 예시: 예산 문제

문제 설명:

• 여러 부서에서 예산을 요청합니다.
• 총 예산이 한정되어 있어, 특정 예산 상한선을 정해서 각 부서가 요청한 예산 중 상한선 이하의 금액을 배정하려고 합니다.
• 상한선을 정해 최대한 많은 부서에 예산을 할당할 때, 상한선의 최대 값을 구합니다.

입력:

• 부서별 예산 요청 리스트
• 총 예산

출력:

• 가능한 예산 상한선의 최대 값

def is_budget_sufficient(budgets, total_budget, cap):
    return sum(min(b, cap) for b in budgets) <= total_budget

def find_max_budget_cap(budgets, total_budget):
    start = 0
    end = max(budgets)
    answer = 0

    while start <= end:
        mid = (start + end) // 2
        if is_budget_sufficient(budgets, total_budget, mid):
            answer = mid
            start = mid + 1
        else:
            end = mid - 1

    return answer

# 예시 입력
budgets = [120, 110, 140, 150]
total_budget = 485

# 예시 출력
print(find_max_budget_cap(budgets, total_budget))  # 출력: 127

 

2-2. 예시: 랜선 자르기

문제 설명:

• 여러 개의 랜선이 있습니다.
• 랜선을 같은 길이로 잘라서, 특정 개수의 랜선을 얻고자 합니다.
• 랜선의 최대 길이를 구합니다.

입력:

• 랜선 길이 리스트
• 필요한 랜선 개수

출력:

• 가능한 최대 랜선 길이

def count_lan_cables(lans, length):
    return sum(l // length for l in lans)

def find_max_lan_length(lans, required_cables):
    start = 1
    end = max(lans)
    answer = 0

    while start <= end:
        mid = (start + end) // 2
        if count_lan_cables(lans, mid) >= required_cables:
            answer = mid
            start = mid + 1
        else:
            end = mid - 1

    return answer

# 예시 입력
lans = [802, 743, 457, 539]
required_cables = 11

# 예시 출력
print(find_max_lan_length(lans, required_cables))  # 출력: 200