[TIL] 탐색 알고리즘- 이진 탐색, 순차 탐색

이진 탐색(Binary Search)

• 작은 문제 해결 후 이를 이용하여 큰 문제를 해결 - 분할 정복
• 정렬된 상태의 리스트를 이용

def bs(data, search):
    if len(data)==1 and search == data[0]:
        return True
    if len(data)==1 and search != data[0]:
        return False
    if len(data) == 0:
        return False

    medium = len(data)//2

    if search == data[medium]:
        return True
    else:
        if search > data[medium]:
            return bs(data[medium+1:], search)
        else:
            return bs(data[:medium], search)

 

이진 탐색의 시간복잡도?
-n개의 리스트를 2로 나눈 후 1이 될 때까지 비교연산 진행
-O(logn+1) = O(logn)

 

순차 탐색(Sequential Search)

• 리스트의 맨 앞부터 차례로 하나씩 비교하여 원하는 데이터를 찾음

 

def sequential(data, search):
    for idx in range(len(data)):
        if data[idx] == search:
            return data[idx]
    return -1

순차 탐색의 시간복잡도?
-최악의 경우 모든 원소를 탐색해야 하므로 O(n)