[Algorithm] 선형 구조에서의 탐색, 선형탐색과 이진탐색

이번 글은 선형구조에서 특정 값을 찾고 싶을 때 어떻게 탐색하는 것이 효율적인가에 대한 알고리즘을 설명합니다. 

 

효율적인 탐색 방법

 

순서

1. 선형탐색과 이진탐색 이론 

2. 파이썬 구현

 

1. 선형탐색과 이진탐색 이론

 

만약 도서관에서 "여덟단어" 책을 찾으려고 할 때 어떻게 찾을 것인가요? 도서관에 책이 왼쪽에서 오른쪽으로 자음 순서대로 있다고 할 때 왼쪽부터 순서대로 찾을 수도 있고 중간 자음인 'ㅅ'을 찾은 후 'ㅅ'을 기준으로 오른쪽 책들만 확인해서 찾아볼 수도 있을 것입니다. 이처럼 왼쪽부터 차례대로 탐색하는 것을 선형탐색 또는 순차탐색, 중간 위치를 찾아서 탐색할 범위를 줄여 탐색하는 것을 이진탐색이라고 합니다. 

 

아래 그림처럼 주어진 데이터를 처음부터 검색하는 것이 선형탐색이고, 

 

선형탐색

 

이진탐색은 정렬된 데이터의 중앙값을 이용해서 탐색합니다. 이진탐색을 할 때는 데이터가 항상 정렬되어있어야 합니다! 정렬이 되어있지 않다면 정렬 알고리즘을 이용하여 정렬한 후 사용해야 합니다. 전체 데이터의 중앙값과 찾고자 하는 값의 크기를 비교하여 찾고자 하는 값이 중앙값보다 크다면 중앙값 기준으로 오른쪽 부분의 데이터를 대상으로 중앙값을 찾고 비교한 후 값을 발견할 때까지 앞의 과정을 반복합니다. 

이진탐색

 

 

그렇다면 선형탐색과 이진탐색 중 어떤 방법이 효율적일까요? 리스트의 길이에 따라 소요되는 시간을 비교해보았습니다. 선형탐색은 최악의 경우가 리스트의 길이에 영향을 받습니다. 만약 위 이진탐색 그림에서 선형탐색으로 10을 찾는다고 가정하면 8개를 모두 탐색해야 하죠? 하지만 이진탐색을 이용하면 3개만 탐색하면 바로 찾을 수 있습니다. 선형탐색은 O(n), 이진탐색은 O(logn)의 시간 복잡도를 가집니다. 차이가 크지 않나요? 상황에 맞게 더 적합한 알고리즘을 사용해야 합니다. 

 

선형탐색과 이진탐색 비교

 

2. 파이썬으로 구현

2.1. 선형탐색

element 가 찾고자 하는 요소, arr이 주어진 리스트일 때 찾고자 하는 원소와 일치하는 원소를 찾으면 인덱스를 리턴하고 리스트를 끝가지 돌았는데 못 찾으면 False를 리턴합니다.

def Sequential_Search(element, arr):
	for i in range(len(arr)):
    	if element==arr[i]:
        	return i 
        return False

2.2 이진탐색

 

중앙값과 찾고자 하는 값을 비교하고 데이터를 쪼개면서 확인하는 과정을 반복합니다.

# index로 접근 
def BinarySearch(element, arr):

    start_index = 0
    end_index = len(arr)-1
    
    while start_index <= end_index:
        mid_point = (start_index + end_index)//2
        
        if arr[mid_point] == element:
            return mid_point
        elif arr[mid_point] > element:
            end_index = mid_point - 1
        elif arr[mid_point] < element:
            start_index = mid_point + 1
    return False
    
    
# 리스트 자체를 반으로 쪼개서 접근 
def BinarySearch(element, arr):

	j = 0
    
    while len(arr) != 0:
        
        mid_point = len(arr)//2
        
        if arr[mid_point] == element:
            j += mid_point
            return j
            
        elif arr[mid_point] > element:
            arr = arr[:mid_point]
            
        elif arr[mid_point] < element:
            arr = arr[mid_point+1:]
        
            j += mid_point +1
    
    return False
            

 

이진탐색은 동일한 과정이 반복되는 규칙을 통해 재귀 함수로도 구현할 수 있습니다. 재귀함수로 구현할 때 이미 문제가 충분히 작아서 바로 답을 알 수 있는 base case는 더 이상 탐색할 범위가 없을 때와 값을 찾았을 때입니다. 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 recursive case는 중앙에 위치한 값이 더 크거나 작을 때입니다. 반복되는 과정이기 때문에 index 만 변경해가며 반복적으로 풀 수 있습니다. 

def BinarySearch(element, arr, start_index = 0, end_index = None):
	
    if end_index == None:  # end_index가 따로 주어지지 않을 때 
    	end_index = len(arr)-1
    
    if start_index > end_index:  # 더 이상 탐색할 범위가 없을 때 
    	return False   
        
    if arr[mid_point] == element:  # 값을 찾았을 때 
    	return mid_point
        
    elif arr[mid_point] > element:
    	return BinarySearch(element, arr, start_index ,mid_point-1)  # end_index update
        
    elif arr[mid_point] < elemet:
    	return BinarySearhc(element, arr, mid_point+1, end_index)  # start_index update