알고리즘 - 선형 탐색 / 이분 탐색

선형 탐색 알고리즘 (Linear Search Algorithm)

---

선형 탐색은 하는 값을 리스트의 맨 앞부터 끝까지 차례대로 찾아 나가는 것이다.

• 시간 복잡도 : O(n)
• 장점 : 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에도 사용 가능하다.
• 단점 : 검색 길이가 길면 비효율적이다.

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

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]))

 

이진 탐색 알고리즘 (Binary Search Algorithm)

---

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘으로 임의의 중간값을 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하는 것이다.

• 시간 복잡도 : O(log n)
• 장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
• 단점 : 정렬된 리스트에만 사용할 수 있다.

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1

    while start_index <= end_index:
        mid_index = (start_index + end_index) // 2

        if element == some_list[mid_index]:
            return mid_index

        elif element < some_list[mid_index]:
            end_index = mid_index - 1
            start_index = mid_index + 1

    return None

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]))

 

참고 블로그

https://minimilab.tistory.com/44

파이썬 선형탐색(Linear Search), 이진탐색(Binary Search)

https://baek.dev/til/algorithm/binary-search

알고리즘 - 선형 탐색 vs 이진 탐색 | 아웃풋 트레이닝