Binary search

정렬된 요소들의 중간값을 기준으로 찾으려는 값과 대소를 비교하여 탐색구간을 조정하고 목표까지 다시 탐색한다.

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

n, target = list(map(int, input().split()))

arr = list(map(int, input().split()))

result = binary_search(arr, target, 0, n-1)
if result == None:
    print('원소없음')
else:
    print(result + 1)

파라메트릭 서치 (Parametric Search)

이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉

파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다
예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다
https://youtu.be/Rr5gMFm588M

bisect 라이브러리

이분탐색을 간결하게 구현하게해주는 라이브러리이다.

bisect() 와 insort() 이 주된 기능인듯하다.

bisect 함수

import bisect

result = bisect.bisect([10,20,30,40],int(input()))

print(result)

입력
35

출력
3

bisect 라이브러리의 bisect 메소드는 정렬된 리스트, 정수를 입력받아
입력된 정수가 리스트에 정렬되어 들어갈 수 있는 인덱스를 리턴한다.

사용하기 좋은 문제 https://www.acmicpc.net/problem/19637

insort 함수

import bisect

a = [10,20,30,40]
bisect.insort(a,int(input()))

print(a)

입력
25

출력
[10,20,25,30,40]

insort함수는 정렬된 리스트와 정수가 입력되었을때
입력된 정수를 리스트의 정렬된 위치에 append한다.

조건에 따라 bisect_left() 또는 insort_left()를 사용해야한다.

참고한 사이트