이진탐색 알고리즘은 어디에? 왜? 쓰는가

이진 탐색(binary search) 알고리즘은 정렬된 데이터 집합에서 원하는 값을 빠르게 찾는 효율적인 탐색 방법입니다.

 

파이썬에서도 이 알고리즘이 널리 사용되며, 주로 다음과 같은 경우에 사용됩니다:

1. 정렬된 리스트에서 특정 값을 찾고자 할 때: 이진 탐색 알고리즘을 사용하면 O(log N)의 시간복잡도로 원하는 값을 찾을 수 있어, 큰 데이터 집합에서 효율적입니다. 이와 달리 선형 탐색 알고리즘은 O(N)의 시간복잡도를 가집니다.
2. 특정 범위에 속하는 값 찾기: 이진 탐색을 사용하여 주어진 범위에 속하는 값들을 빠르게 찾을 수 있습니다.
3. 이산화(discretization) 문제 해결: 숫자를 구간별로 이산화하여 어떤 구간에 속하는지 빠르게 알아내는 데 이진 탐색이 사용됩니다.
4. 이진 탐색을 활용한 최적화 문제: 파라메트릭 서치(parametric search)와 같은 최적화 문제에서 이진 탐색을 사용하여 솔루션을 빠르게 찾을 수 있습니다.

파이썬에서는 bisect 모듈을 사용하여 이진 탐색을 쉽게 구현할 수 있습니다. 이 모듈은 정렬된 시퀀스에서 원하는 값의 위치를 찾아주는 함수와 값을 삽입할 위치를 찾아주는 함수를 제공합니다.

이진 탐색 알고리즘은 정렬된 데이터 집합에서 원하는 값을 빠르게 찾을 수 있는 효율적인 방법으로, 다양한 상황에서 사용되어 시간과 자원을 절약할 수 있습니다.

 

 

def insert_in_sorted_list(arr, new_val):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == new_val:
            arr.insert(mid, new_val)
            return
        elif arr[mid] < new_val:
            left = mid + 1
        else:
            right = mid - 1
            
    arr.insert(left, new_val)

 

리스트의 insert를 활용하여 이진탐색 이후 빈 자리에 원소를 넣어주는 알고리즘입니다.

 

중요한 것은 사전에 정렬된 상태의 리스트가 입력되어야 한다는 점을 유의합니다.