순차 탐색, 이진 탐색 정리

👩‍💻 순차 탐색(Sequential Search)과 이진 탐색(Binary Search) 정리

 

🥘 순차 탐색(Sequential Search)

데이터가 담겨있는 리스트를 앞에서부터 하나씩 살펴보아서 원하는 데이터를 찾는 방법입니다.

 

🍀 순차 탐색 코드

def sequentialSearch(list, search):
    for index in range(len(list)):
        if list[index] == search:
            return True
    return False

 

☘️ 순차 탐색 시간 복잡도

찾고자 하는 값이 리스트의 맨 마지막에 있을 때, 리스트의 길이만큼 데이터를 비교해야 합니다.

따라서 시간 복잡도는 O(n)입니다.

 

🍳 이진 탐색 (Binary Search)

탐색할 데이터를 정확히 반으로 나누어 한쪽에 데이터가 없다면 한쪽을 버리면서 탐색하는 방법입니다.

단, 이진 탐색은 데이터가 미리 정렬되어 있어야지 사용할 수 있습니다.

 

🍀 이진 탐색 코드

def binarySearch(list, search):
    print(list)
    if len(list) == 1 and list[0] == search:
        return True
    if len(list) == 1 and list[0] != search:
        return False
    if len(list) == 0:
        return False

    medium = len(list) // 2
    if list[medium] == search:
        return True
    else:
        if list[medium] < search:
            return binarySearch(list[medium + 1:], search)
        else:
            return binarySearch(list[:medium], search)

 

☘️ 이진 탐색 시간 복잡도

리스트를 매번 2개로 나누어 1이 될 때까지 비교 연산을 진행하기 때문에 시간 복잡도는 O(log n)입니다.