Algorithm, Python 이분 탐색(Binary Search)

이분 탐색(Binary Search)

- 정렬된 배열에서 특정한 값을 효율적으로 찾는 알고리즘

- 탐색 범위를 반으로 줄여가면서 원하는 값을 찾는 것

- 정렬된 배열에서 매우 빠르게 원하는 값을 찾을 수 있음.

- 큰 데이터에서 특정 값을 찾을 때 유용

- 기본 절차

1. 배열의 가장 낮은 인덱스(low)와 가장 높은 인덱스(high)를 설정.
2. low가 high보다 작거나 같은 동안 반복.
3. 중간 인덱스(mid)를 찾는다. 일반적으로 mid = (low + high) // 2로 계산.
4. 중간 인덱스의 값(array[mid])이 찾고자 하는 값(target)과 같으면 위치를 반환.
5. 만약 array[mid]가 target보다 작으면, low를 mid + 1로 설정.
6. 만약 array[mid]가 target보다 크면, high를 mid - 1로 설정.
7. 2번으로 돌아가 반복.

- 이분 탐색 구현 기본 예제 코드 / 시간 복잡도 O(log n)

def binary_search(array, target):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # 타겟을 찾지 못한 경우

# 예제 사용
array = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(array, target)

if result != -1:
    print(f"타겟은 인덱스 {result}에 위치.")
else:
    print("타겟을 찾을 수 없음.")

 

bisect 모듈

- 이진 탐색과 정렬된 배열에 관련된 함수들을 제공

- 특정 값이 배열에서 어느 위치에 삽입되어야 하는지를 효과적으로 찾을 수 있음.

- 자주 사용하는 함수로는 bisect_left, bisect_right, insort_left, insort_right 등

- 주로 정렬된 순서를 유지하면서 배열에 값을 삽입하거나 해당 값의 위치를 찾는 데 사용.

from bisect import bisect_left, bisect_right, insort_left, insort_right

# 정렬된 배열
arr = [1, 2, 4, 4, 4, 6, 8]

# bisect_left: 특정 값이 삽입되어야 하는 왼쪽 인덱스 반환
index_left = bisect_left(arr, 4)
print(f"bisect_left: {index_left}")

# bisect_right: 특정 값이 삽입되어야 하는 오른쪽 인덱스 반환
index_right = bisect_right(arr, 4)
print(f"bisect_right: {index_right}")

# insort_left: 정렬된 순서를 유지하면서 특정 값 삽입
insort_left(arr, 5)
print(f"insort_left: {arr}")

# insort_right: 정렬된 순서를 유지하면서 특정 값 삽입
insort_right(arr, 4)
print(f"insort_right: {arr}")