이진 탐색

순차 탐색

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i+1
            
n, target = input().split()
n = int(n)
array = input().split()

print(sequential_search(n, target, array))

이진 탐색

• 이진 탐색 : 데이터가 정렬되어 있을 때, O(logN)의 시간복잡도로 탐색을 구현하는 방법

재귀함수를 이용한 이진탐색

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, mid+1, end)
    else:
        return binary_search(array, target, start, mid-1)

n, target = map(int, input().split())
array = list(map(int, input().split()))
result = binary_search(array, target, 0, len(array))
if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

for문을 이용한 이진 탐색

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

n, target = map(int, input().split())
array = list(map(int, input().split()))
result = binary_search2(array, target, 0, n-1)
if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

• 이진탐색은 코딩테스트에서 단골로 나오는 문제이니 외우는 것이 좋다!

파라메트릭 서치

• 파라메트릭 서치 : 최적화 문제를 결정 문제(예 or 아니오)로 바꾸어 해결하는 기법
• 1~10억까지의 큰 수를 보면 당연하다는 듯이 이진 탐색을 떠올려야 한다.
• 이진탐색에 파라메트릭 서치 기법을 적용하면 된다.