이진탐색

이진 탐색

• 탐색할 자료를 둘로 나누어 탐색

분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘 (Divide & Conquer)
  • Divide : 문제를 하나 또는 둘 이상으로 나눈다.
  • Conquer : 나눠진 문제가 충분히 작고, 해결 가능하다면 해결, 아니면 다시 나눈다.
• 이진 탐색
  • 정렬된 상태에서 진행
  • Divide : 리스트를 두 개의 서브 리스트로 나눈다.
  • Conquer
    • search > 중간값 이면, 뒤에서 찾는다. 반대면 앞에서 찾는다.

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

알고리즘 분석

• n 개의 리스트를 매번 2로 나누어 1이 될때까지 비교연산
  • n x (1/2)^k (k회 진행)
  • log2n = k
  • O(logN)의 시간 복잡도를 갖는다.

순차 탐색

• 앞에서부터 하나씩 비교해서 데이터 탐색

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

알고리즘 분석

• 최악의 경우 모두 비교하므로, 시간복잡도는 O(N)