이진탐색 이론

이진탐색은 이미 정렬되어 있는 데이터에서 절반씩 좁혀가며 탐색하는 방법

 

"이미 정렬",  "절반씩"

0~10억 같은 큰 탐색범위를 보면 가장 먼저 이진탐색을 떠올려라

 

 

 

python에서 이진탐색 구현

---

def binary_search(data, target, start, end):
    if start > end:
        return None
    mid = (start+end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        return binary_search(data, target, start, mid-1)
    else:
        return binary_search(data, target, mid+1, end)


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("X")
else:
    print(result + 1)

 

python 이진탐색 라이브러리 bisect

---

 

임포트

from bisect import bisect_left, bisect_right

 

설명

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환한다.
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환한다.

 

 

 

사용예시

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

출력

2
4

 

 

파라메트릭 서치

---

최적화 문제를 '예' '아니오'로 바꾸로 해결하는 기법

 

예시) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화문제