[알고리즘] 선형탐색과 이진탐색

 

선형탐색 : 리스트가 정렬되지 않았을 경우 사용, 최악의 경우 리스트의 길이 만큼 반복해야함

이진탐색 : 리스트가 정렬되어있을 경우 사용 (탐색해야 하는 데이터의 개수나 값이 많을 경우) 

---

 

1. 선형탐색

'선형 탐색(Linear Search)' 이란, 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘

예제)

def linear_search(element, some_list):
    # 여기에 코드를 작성하세요

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

 

실행결과)

0
None
2
1
4

 

답안)

def linear_search(element, some_list):
    # 여기에 코드를 작성하세요
    for idx, val in enumerate(some_list):
        if element==val:
            return idx
    return None

 

시간복잡도)

선형탐색은 반복 횟수가 리스트 길이에 비례하기 때문에 시간 복잡도는  O(N) 임. 

 

 

 

 

 

2. 이진탐색

'이진 탐색(Binary Search)’  알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능하다.

문제)

 [1, 2, 3, 5, 8, 13, 21, 34, 55]에서 3을 찾는 경우

 

시도1)

리스트의 첫 번째 인덱스와 마지막 인덱스의 값을 합하여 2로 나눈 후, 중간 인덱스로 지정한다. 그리고 그 인덱스에 해당하는 값이 3인지 확인한다.

 

이 경우 리스트의 첫 번째 인덱스는 0이고 마지막 인덱스는 8이기 때문에, 중간 인덱스는 4이고 해당 원소는 8이다. 찾고자 하는 원소(3)는 중간 원소(8)에 비해 작다. 리스트는 정렬되어 있으니, 이제 인덱스 4~8은 탐색 범위에서 제외시킬 수 있습니다. 탐색 범위가 절반으로 줄어든 것이다.

 

시도2)

탐색 범위는 이제 인덱스 0~3인데, 탐색 범위의 첫 번째 인덱스는 0이고 마지막 인덱스는 3이기 때문에, 중간 인덱스는 (0 + 3) // 2인 1이다. 인덱스 1에 해당하는 원소는 2이다.

 

찾고자 하는 원소(3)는 중간 원소(2)에 비해 크다. 리스트는 정렬되어 있으니, 이제 인덱스 0~1은 탐색 범위에서 제외시키면 된다. 탐색 범위가 다시 절반으로 줄어든 것이다.

 

시도3)

탐색 범위는 이제 인덱스 2~3이다. 탐색 범위의 리스트의 첫 번째 인덱스는 2이고 마지막 인덱스는 3이므로, 중간 인덱스는 (2 + 3) // 2인 2입니다. 인덱스 2에 해당하는 원소의 값은 3이다.

 

찾고자 하는 원소(3)는 중간에 해당하는 원소(3)와 일치한다. 값을 찾았으니, 인덱스 2를 리턴해 준다.

 

 

 

 

예제)

def binary_search(element, some_list):
    # 여기에 코드를 작성하세요

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

실행결과)

0
None
2
1
4

 

 

답안)

def binary_search(element, some_list):
    start = 0
    end = len(some_list) - 1
    
    while start <= end:
        mid = (start + end) // 2
        
        if some_list[mid] < element:
            start = mid + 1
        elif some_list[mid] > element:
            end = mid - 1
        elif some_list[mid] == element:
            return mid
        
    return None

 

 

 

시간복잡도)

이진 탐색은 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도는  O(log N) 임. 확인하는 데이터의 개수가 절반씩 줄어드는 특징은 퀵 정렬과 동일