1. 선형 탐색과 이진 탐색

선형 탐색(Linear Search)색(Linear Search)

선형 탐색이란, 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘입니다.

 

선형 탐색 알고리즘

def linear_search(element, some_list):

    for i in range(len(some_list)):
        if element == some_list[i]:
            return i
    return None

i = 0 부터 끝까지 순서대로, 해당 인덱스의 값과 element가 같은지 비교합니다.

 

이진 탐색(Binary Search)

이진 탐색이란, 리스트의 중앙값을 계속 확인하며 특정값과 비교하는 방법입니다.

 

이진 탐색 알고리즘

* 주의 할 점은, 이진 탐색 알고리즘은 list가 sort 되어 있는 상태에서만 가능하다는 것입니다.

 

우선 첫 번째 인덱스와 마지막 인덱스를 아래와 같이 설정합니다.

min_idx = 0
max_idx = len(some_list)-1

 

범위를 줄여나갑니다.

binary_idx는 중앙값의 index를 의미하고, 첫 번째 인덱스와 마지막 인덱스를 더하여 2로 나눈 몫을 할당해 줍니다.

while의 조건부는 min__idx와 max_idx가 엇갈리는 순간이 올 것을 대비해 다음과 같이 설정해 줍니다.

while min_idx <= max_idx:
    
        binary_idx = (min_idx + max_idx) // 2

 

만약, 중앙값이 찾고자 하는 특정값보다 크다면, 중앙값보다 특정값이 앞에 위치하므로 중앙값의 인덱스에서 1을 빼준 숫자를 max_idx에 넣어 중앙값 인덱스 이전 부분만 탐색하도록 범위를 줄여준다.

 

반대의 경우 중앙값 인덱스에 1을 더한 값을 min_idx에 넣어 중앙값 인덱스 이후 부분만 탐색하도록 범위를 줄여준다.

 

만약 중앙값과 특정값이 같아서 드디어 위치를 찾아냈다면 binary_idx를 return한다. 

if some_list[binary_idx] > element:

	max_idx = binary_idx - 1
            
elif some_list[binary_idx] < element:

	min_idx = binary_idx + 1
            
elif some_list[binary_idx] == element:

	return binary_idx

 

이진탐색 알고리즘 입니다.

def binary_search(element, some_list):

    min_idx = 0
    max_idx = len(some_list)-1
    
    while min_idx <= max_idx:
    
        binary_idx = (min_idx + max_idx) // 2
        
        if some_list[binary_idx] > element:
            max_idx = binary_idx - 1
            
        elif some_list[binary_idx] < element:
            min_idx = binary_idx + 1
            
        elif some_list[binary_idx] == element:
            return binary_idx
            
    return None  

---

선형탐색 알고리즘과 이진탐색 알고리즘 중 어떤 것이 더 효율적일까요?

 

탐색 범위가 크지 않다면 탐색하고자하는 특정값의 위치에 따라 어느 것이 더 효율적인지가 다를 것 입니다.

 

예를 들어, length가 16인 list가 있다고 가정해 봅시다.

특정값이 2일 경우, 제일 앞에서부터 탐색하는 선형 탐색 알고리즘이 한 번의 시도만에 특정값의 위치를 찾아낼 것입니다.

그러나 특정값이 53일 경우 이진 탐색 알고리즘이 4번만에 특정값의 위치를 찾아내는 것에 비해, 선형 탐색 알고리즘은 16번만에 찾아내겠죠.

 

list의 길이가 길어질 수록 둘의 효율성은 극명하게 차이를 보여줍니다.

 

Facebook의 경우 23억명의 유저가 있는데요.

선형 탐색 알고리즘을 사용하면 최악의 경우 23억명을 탐색해야 합니다.

그러나 이진 탐색 알고리즘을 사용하면 최악의 경우에도 31명을 탐색하는 것으로 족합니다.

 

---

선형 탐색과 이진 탐색의 Big-O notation