[선형탐색/이진탐색] 탐색 기법 비교

선형탐색은 앞에서부터 순차적으로 찾고자 하는 값을 찾는 방식이다. 리스트가 굳이 정렬될 필요가 없다. 

이진탐색은 중간값을 기준으로 찾고자 하는 값을 찾는 방식이다. 정렬된 리스트값에서 중간값을 기준으로 찾고자 하는 값을 찾는 방식이다. 찾고자 하는 값이 중간에 있는 값보다 크다면, 추후에는 오른쪽을 탐색한다. 중간값을 기준으로 탐색 범위가 절반으로 줄어들기 때문에 이진탐색(binary)이라는 이름이 붙였다. 

 

선형탐색 시간은 리스트의 길이가 늘어날 수록 그 길이만큼 늘어나는 것에 반해, 이진탐색은 리스트의 길이가 늘어나는 거에 비해서 천천히 늘어난다. 다만, 이진탐색은 정렬된 리스트에 한해서 찾을 수 있기 때문에, 정렬되지 않은 리스트를 탐색하기 위해서는 선형탐색을 사용할 수 밖에 없다.

 

연습문제

Q. n개의 정수로 구성된 정렬 상태의 배열을 임의 횟수 만큼 회전(정렬된 상태에서 시작하는 숫자가 순차적으로 달라진다) 시켜 얻은 배열이 입력으로 주어진다고 하자. 이 배열에서 특정한 원소를 찾는 알고리즘을 고안하라. 회전시키기 전에, 원래 배열은 오름차순으로 정렬되어 있다. 

 

위의 문제의 경우 회전된 상태이기 때문에 5의 위치를 찾고자 하는 경우, 이진탐색의 문제처럼 5와 중간값을 비교해본다고 생각해보자. 

list_ro = [10, 11, 13, 15, 20, 1, 3, 5,7, 9] 의 경우 중간값 list_ro[4] = 20을 단순히 비교해서는 구할 수 없다. 

중간값 이전의 리스트 부분에 5가 없기 때문이다. 따라서, 이 경우에는 오름차순으로 제대로 배열되어 있는 부분이 어디인지 보는 것부터 우선으로 한다. 리스트의 첫번째값 10과 중간값 20, 그리고 마지막 값 9를 보면 중간값 이전은 제대로 배열되어 있으나, 그 이후의 값은 제대로 배열되어 있지 않다.

 

중간값과 시작값, 그리고 마지막값의 범위 안에 우리가 찾고자 하는 값이 있는지 먼저 찾아야 한다. 

def search_rotate(element, ori_l):
    start = 0
    end = len(ori_l)-1
    
    while start <= end:     
        middle = (start+end) //2        
        if ori_l[middle] ==element:
            return middle
        elif ori_l[start] =< element < ori_l[middle]:
            end = middle -1
        elif ori_l[middle] < element <= ori_l[end]: #끝값들을 탐색하는데 포함해야 하므로 "="을 꼭 넣어줘야 한다. 
            start = middle+1
        else: 
            return "None" #만약에, 위의 경우의 수에 모두다 해당하지 않으면, None입력하고 빠져나오기
            break    
    
    return None

search_rotate(5, [15, 16, 19, 20, 25, 1,3,4,5,7, 10, 14])