탐색 알고리즘 - 선형탐색, 이진탐색, 이진트리 탐색

1. 선형탐색(Linear Search Algorithm / Sequential Search Algorithm)

- 리스트에서 특정한 값을 찾는 알고리즘의 하나. 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나간다.

- 검색할 리스트의 길이가 길면 비효율적이지만, 검색방법 중 가장 단순하여 구현이 쉽고, 정렬되지 않은 리스트에서도 사용할 수 있다.

- 예를 들어, 알파벳_list라는 리스트가 있다고 치자.

알파벳_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

이렇게 10개의 알파벳 string을 가지고 있다.

이 경우 우리가 하나의 알파벳을 뽑아낸다고 할 때, 최고의 경우(best case)는, 'a'를 뽑아낼 때이다. 뽑아보자.

def get_alphabet(찾으려는_알파벳):
    for alphabet in 알파벳_list :
    if alphabet == 찾으려는_알파벳:
        return alphabet
    return None
                    
>>> get_alphabet('a')

a는 alphabet_list가 for loop를 첫 번째 도는 순간 출력된다.

그러나 'j', 즉 최악의 경우(worst case)에는?

>>> get_alphabet('j')

당연히 for loop의 끝까지 돈 후에야 알파벳을 찾아낸다.

물론 위의 list는 너무나 짧아서 'a'를 찾으나 'j'를 찾으나 걸리는 시간은 거의 0에 수렴한다.

하지만 list의 길이가 늘어나면 늘어날수록 시간차는 벌어진다.

선형탐색 알고리즘의 시간복잡도는 O(n).

2. 이진탐색(Binary Search)

- 사전에서 단어찾기를 생각하면 쉽다!(앞뒤로 비교하며 차차 찾아가는 과정)

- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 

- 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 

- 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

def binarySearch(array, value, low=0, high=0):
    if low > high:
        return False
     mid = (low+high) // 2
     if array[mid] > value:
           return binarySearch(array, value, low, mid-1)
     elif array[mid] < value:
        return binarySearch(array, value, mid+1, high)
    else:
        return mid

3. 이진트리 탐색(Binary Tree Search)

- 이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.

1) 중위순회(in-order) : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.

2) 전위순회(pre-order) : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.

3) 후위순회(post-order) : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.