순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

예시

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 = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
print(result + 1)

시간 복잡도

이진 탐색은 범위를 절반씩 줄이며 탐색하기 때문에 O(logN)을 보장합니다.

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

파라메트릭 서치

파라메트릭 서치란 최적화 문제를 결정 문제('예', '아니오')로 바꾸어 해결하는 기법

• 일반적인 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능

예제

1.

💡아이디어

N, M = map(int, input('입력 = ').split())
array = list(map(int, input().split()))

temp = [i for i in range(max(array)+1)]

result = []
while True:
    if len(temp) == 0:
        print(result[len(result)-1])
        break

    mid = len(temp) // 2
    total = sum([i - temp[mid] for i in array if i > temp[mid]])

    if total == M:
        print(temp[mid])
        break
    elif total < M:
        temp = temp[:mid]
    else:
        result.append(temp[mid])
        temp = temp[mid+1:]

먼저 1부터 array의 max값만큼의 요소를 갖는 temp를 만든다. 그리고 temp의 중간 index인 mid를 정의한다.

total에는 절단기보다 떡의 길이가 짧을 경우 잘리지 않을테니 해당 경우를 제외하기위해 조건문을 달아 잘린 떡의 길이를 구한다.

total이 M과 같다면 정답이니 바로 출력한다. 만약 M보다 total이 작다면 절단기의 길이를 더 줄여야하니 temp의 범위를 줄이고, M보다 total이 크다면 절단기의 길이를 늘려야하니 범위를 늘린다. 후자의 경우 적어도 M만큼의 떡을 가져가야한다는 조건이 있기 때문에 M과 가장 가까운 떡의 양을 얻을 수 있는 값을 구하기위해 result에 추가한다.

만약 total과 M이 같은 값이 없다면 result의 마지막 값이 그나마 조건을 충족하는 가장 가까운 값이 되기 때문에 이를 출력한다.

2.

💡아이디어

from bisect import bisect_left, bisect_right

N, M = map(int, input('입력 = ').split())
array = list(map(int, input().split()))

left = bisect_left(array, M)
right = bisect_right(array, M)

if right-left == 0:
    print(-1)
else:
    print(right-left)

이 문제는 파이썬의 bisect를 이용하면 정말 쉽게 풀 수 있다. bisect_left와 bisect_right는 리스트에서 지정한 문자를 이진 탐색하여 각각 왼쪽과 오른쪽 index를 반환해준다. 고로 정렬된 리스트라면 오른쪽 - 왼쪽을 했을 때 수가 존재한다면 0보다 큰 수가 나올테고 수가 존재하지 않는다면 0이 나올 것이다.