[알고리즘] 02. 탐색 알고리즘

13 Jan 2020 in Computer-Science

다양한 탐색 알고리즘의 특징을 살펴본다.

여러 데이터 중 특정 값을 찾아내는 여러 알고리즘을 살펴본다.

1. 순차 탐색

1. 데이터의 첫번째 인덱스부터 하나씩 비교하여 원하는 데이터를 찾는다.

2. 이진 탐색

def binary_search(lst, data):
    lst.sort()
    left, right = 0, len(lst)
    while True:
        mid = (left + right)//2
        if lst[mid] == data:
            return lst[mid]
        elif lst[mid] < data:
            left = mid + 1
        elif lst[mid] > data:
            right = mid

        if left == right:
            return False

1. 데이터가 정렬되어 있을때, 데이터의 중앙값을 원하는 값과 비교한다.

2. 1에서 비교한 값이 원하는 값보다 크면 앞쪽 데이터에서 1의과정을 반복하면 작으면 뒷쪽 데이터에서 1의 과정을 반복한다.

3. 원하는 값을 찾을때까지 1~2의 과정을 반복한다.

3. 순차 탐색과 이진 탐색 비교