Binary Search(이분탐색)

##개념

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
• 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고있다.
• 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
• 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만
• 검색이 반복될 때 마다 목표 값을 찾을 확률은 두 배가 되기 때문에 속도가 빠르다는 장점이 있다.

특징

• 시간복잡도는 O(logN)이다.
• 단계마다 탐색 범위를 반으로 나누는 것과 동일하기 때문에 상기의 시간 복잡도를 가지게 된다.
• 예를 들어 처음 데이터 개수가 32개라면, 1단계를 거치면 16개가 남고, 2단계에서 8개, 3단계에서 약 4개의 데이터만 남는다.
• 즉, 이분 탐색은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다.

# Binary Search 구현
# 탐색할 배열
arr = [1, 4, 7, 9, 11, 13, 16, 17, 21, 22, 25, 28]

# - Parameter key: 찾아야 하는 값
#             arr: 탐색할 배열
def binary_search(key: int, arr: [int]):
    # 오름차순으로 정렬
    arr.sort()
    # 첫 번째 인덱스를 왼쪽으로 잡는다.
    left = 0
    # 마지막 인덱스를 오른쪽으로 잡는다.
    right = len(arr) - 1

    # 왼쪽이 오른쪽 이하인 경우
    while left <= right:
        # 중간 값을 구한다. (괄호 꼭 잘 확인할 것)
        mid = int((left + right) / 2)
        # 만약 중간 값과 key값이 같다면
        if arr[mid] == key:
            # 출력
            print(mid)
            # 반복문 브레이크
            break
        # 만약 중간 값이 찾는 값 보다 크다면
        elif arr[mid] > key:
            # 오른쪽 값을 중간 - 1 값으로 설정 (mid도 탐색 범위가 아니기 때문)
            right = mid - 1
        # 만약 중간 값이 찾는 값 보다 작다면
        else:
            # 왼쪽 값을 중간 + 1 값으로 설정 (mid도 탐색 범위가 아니기 때문)
            left = mid + 1

binary_search(key=22, arr=arr)

입국심사

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

3079번: 입국심사

# baekjoon 3079 입국심사
# 친구 M명 (최대 10억명)
# K번 심사대에 앉아있는 심사관이 한 명을 심사하는데 걸리는 시간 Tk
# N입국 심사 10만 친구 10억명 친구만 선형탐색 해도 시간초과가 발생한다.
# 완전탐색으론 풀 수 없고, 그래프도 아니고, 선형적인 자료가 있는 투포인터도 아니고
# 그리디나 이진탐색으로 생각해볼 수 있다.
# 최대 시간이 걸리는 경우는 제일 많이 걸리는 곳에서 입국심사를 모두가 받는 경우다.
# 최대 최소 값 설정 잘하기 
import sys
n, m = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline()) for _ in range(n)]
left = min(arr)
right = max(arr) * m
ret = right

# Check 함수를 잘 짜는 것이 이진 탐색에서 가장 중요하다.
def check(arr: [int], mid_val: int) -> bool:
    cnt = 0
    for i in range(n):
        # 주어진 시간에서 각 검사대가 끝낼 수 있는 최대 인원수 를 더해준다.
        cnt += mid // arr[i]

    # 친구의 숫자 보다 각 검색대에서 검사할 수 있는 최대 인원이 큰 경우 True 리턴
    if cnt >= m:
        return True
    # 아닌 경우는 False 리턴
    return False

while left <= right:
    # 중간  값을 구한다.
    mid = (left + right) // 2
    # 최대 시간 안에 끝낼 수 있으면
    if check(arr, mid):
        # 시간을 더 줄인다.
        right = mid - 1
        ret = min(ret, mid)
    else:
        # 시간안에 못 끝내면 시간을 늘린다.
        left = mid + 1

print(ret)