[알고리즘] 이분 탐색

이분 탐색(Binary Search)은 정렬된 리스트나 배열에서 특정한 값을 찾는 알고리즘입니다. 이 알고리즘은 탐색 범위를 반으로 분할하면서 값을 찾아 나갑니다. 이분 탐색은 시간 복잡도 O(log n)으로 매우 효율적인 탐색 알고리즘입니다.

아래는 이분 탐색을 파이썬으로 구현한 예시입니다:

def binary_search(arr, target):
    left = 0
    right = 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

    return -1

# 예시로 정렬된 리스트를 사용합니다.
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]
target = 40

result = binary_search(arr, target)
if result != -1:
    print(f"타겟 {target}은 인덱스 {result}에 위치합니다.")
else:
    print("타겟을 찾을 수 없습니다.")

위의 예시에서는 binary_search() 함수를 사용하여 정렬된 리스트 arr에서 target 값을 찾습니다. 초기에는 전체 리스트를 탐색 범위로 설정하고, 반복문을 통해 탐색 범위를 반으로 분할하면서 target 값을 찾아 나갑니다. left와 right 변수는 탐색 범위의 왼쪽과 오른쪽 인덱스를 나타내며, mid 변수는 중간 인덱스를 계산합니다.

탐색 범위를 반으로 분할하면서 arr[mid]와 target 값을 비교하여 탐색을 진행합니다. arr[mid]가 target와 같으면 mid 인덱스를 반환하고, arr[mid]가 target보다 작으면 left를 mid + 1로 업데이트하여 오른쪽 부분 리스트를 탐색하고, arr[mid]가 target보다 크면 right를 mid - 1로 업데이트하여 왼쪽 부분 리스트를 탐색합니다.

만약 탐색을 마치고도 target을 찾지 못하면 -1을 반환하여 타겟을 찾을 수 없다고 알려줍니다.

위의 예시에서는 arr 리스트에서 target 값인 40을 찾고, 결과로서 "타겟 40은 인덱스 3에 위치합니다."라고 출력됩니다.

 

다음은 이분 탐색을 이용한 코딩 테스트 문제의 해법입니다. 

문제는 https://school.programmers.co.kr/learn/courses/30/lessons/43238 를 참조하세요.

def binarySearch(left, right, times, n):
    cnt=0
    answer = -1
    while left <= right:
        mid = int((left+right)/2) #중간 값을 정해 봄
        cnt = 0
        for time in times:
            cnt += int(mid/time)  #중간 값에서 처리할 수 있는 사람 수

        if cnt >= n: 
            if answer == -1:
                answer = mid
            else:
                answer = min(answer,mid)
            right = mid-1
        elif cnt < n: left = mid+1
            
    return answer

def solution(n, times):
    times.sort()
    left = 0
    right = times[-1]*n # 최악의 시간 계산
    answer = binarySearch(left, right, times, n)
    print(answer)
    return answer

 

 

[참조]

https://school.programmers.co.kr/learn/courses/30/lessons/43238/solution_groups?language=python3