선형 탐색(Linear search)

배열은 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘
선형탐색 코드구현

def linear_search(array, search_value):
    for i in range(len(array)):
        if search_value == array[i]:
            return i      # 요소가 존재하면 해당 index값 출력
    return None           # 요소가 존재하지 않으면 None 출력

print(linear_search([2, 3, 5, 7, 11],2))   # 0
print(linear_search([2, 3, 5, 7, 11],0))   # None
print(linear_search([2, 3, 5, 7, 11],5))   # 2
print(linear_search([2, 3, 5, 7, 11],3))   # 1
print(linear_search([2, 3, 5, 7, 11],11))  # 4

이분 탐색(Binary search)

정렬된 배열(Sorted array, Ordered array)에서만 사용가능하다
정렬된 자료를 반으로 나누어 탐색하는 방법
이진탐색 코드구현

def binary_search(array, search_value):
		# 최초의 상한선은 배열의 첫 번째 인덱스, 하한선은 마지막 인덱스
    lower_bound = 0
    upper_bound = len(array) - 1

		# 상한선과 하한선 사이의 가운데 값을 계속해서 혹인하는 루프
    while lower_bound <= upper_bound:
        midpoint = (upper_bound + lower_bound) // 2

        value_at_midpoint = array[midpoint]

        if search_value == value_at_midpoint:
            return midpoint
        elif search_value < value_at_midpoint:
            upper_bound = midpoint - 1
        elif search_value > value_at_midpoint:
            lower_bound = midpoint + 1

print(binary_search([3,17,75,80,202],22)) # 'None' 출력
print(binary_search([3,17,75,80,202],17)) # '1' 출력

이진 탐색 vs 선형 탐색

선형검색은 최대 모든 셀을 확인해야하지만, 이진 검색의 경우 추측할 때 마다 검색해야 할 셀 중 절반을 제거할 수 있다(log(n))
선형검색은 데이터를 두배로 늘릴 때마다 최대 단계도 두 배 증가하지만, 이진검색의 경우 최대 단계에 하나만 더 추가하면 된다
검색이 많은 자료라면 정렬을 먼저 한 다음 이진검색을 하는 것이, 검색이 많지않고 데이터를 추가하기만 한다면 정렬을 하지 않고 삽입을 더 빠르게 처리하는 것이 더 나을수 있다

Untitled