[코딩 + 알고리즘 완주반] 19일차. 이진탐색( Binary Search ), 순차탐색 ( Sequential Search )

# 이진 탐색

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

 

 

# 분할 정복 알고리즘

divide : 문제를 하나 또는 둘 이상으로 나눈다

conquer :  나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다

 

# 이진탐색

divide : 리스트를 두 개의 서브 리스트로 나눈다

conquer : 검색할 숫자 > 중간값이면 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다

                검색할 숫자 < 중간값이면 앞부분의 서브 리스트에서 검색할 숫자를 찾는다

 

# 알고리즘 구현

def binary_search(data, search):
    print (data)
    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 binary_search(data[medium+1:], search)
        else:
            return binary_search(data[:medium], search)

# 이진탐색 시간복잡도

n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산 k회 진행

O(logn)

 

# 순차 탐색 ( Sequential Search )

데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

 

def sequencial(data_list, search_data):
    for index in range(len(data_list)):
        if data_list[index] == search_data:
            return index
    return -1

# 순차 탐색 시간 복잡도

최악의 경우 리스트가 n일 때 n번 비교

O(n)