[알고리즘/Python] 이진 탐색

1. 개요

• 정렬된 배열에서 '특정 값'을 찾는 알고리즘을 의미합니다.
• O(logn)으로 빠른 속도를 보장합니다.

2. 이진 탐색의 동작 과정

arr [1, 3, 5, 8, 11, 15, 30, 32, 45]이거 key값이 8인 경우 이진 탐색을 찾는 원리를 확인

1. 배열의 ‘중간 값’을 선택하여 찾고자 하는 값과 비교합니다. 

2. 만약 중간 값이 찾고자 하는 값보다 크면 ‘배열 왼쪽 부분'에서 탐색을 진행하고, 값보다 작으면 ‘배열 오른쪽 부분'에서 탐색을 진행합니다. 

3. 이 과정에서 찾고자 하는 값이 나올 때까지 반복합니다

이진 탐색 코드

이진 탐색 소스코드: 재귀적 구현(Python)

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
	elif array[mid] >= target:
    	return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    else:
        return binary_search(array, target, mid+1, end)
    
# n의(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 안습니다.")
else:
    print(result + 1) 
    

파이썬 이진 탐색 라이브러리

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 오른쪽 인덱스 반환
• 두 인덱스의 차이는 배열에서 두 원소사이의 원소의 개수 return

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, left_value, right_value)
    left_index = bisec_left(a, left_value)
    return right_index - left_index

# 배열 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_by_range(a, 4, 4))
print(count_by_range(a, -1, 3))

# 실행결과
2, 6