탐색 알고리즘 - 선형탐색과 이진 탐색

🎯 탐색

📌 선형탐색 (순차 탐색)

⭐ 정렬되지 않은 data set에도 사용할 수 있다.
따라서 정렬되어 있지 않을 때 사용한다.
순차적으로 모든 요소를 탐색하기 때문에 순차 탐색이라고 부른다.

선형 탐색 시간 복잡도

평균의 경우 : O(n/2)
최악의 경우 : O(n)

기본 알고리즘

def linear_serch(a_list,n):
    for i in a_list:
        if i == n :
            return True
    return False

x1 = [1,5,4,6,7,21]
a = 7
b = 9
print(linear_serch(x1,a))
print(linear_serch(x1,b))

👉 실행화면

True
False

파이썬의 in 키워드를 이용한 알고리즘

# 파이썬의 in 키워드를 이용한 선형 탐색
print(a in x1)
print(b in x1)

👉 실행화면

True
False

📌 이진 탐색

정렬된 데이터 세트의 중간값을 기준으로 검색 대상을 반씩 줄여 나간다.
⭐ 데이터가 정렬된 상태에서만 사용할 수 있다.

이진 탐색 시간 복잡도

• O(log n)
• 최악의 경우 필요한 단계 구하기 : 2**n = 데이터크기

👍 효과적으로 시간을 단축하기 때문에 정렬 자체에 시간이 걸리더라도 정렬 후 이진 탐색을 고려해볼만 하다.

기본 알고리즘

def binary_search(a_list,n):
    first = 0
    last = len(a_list) - 1
    while first <= last:
        mid = (first+last) //2
        if a_list[mid] == n :
            return True
        elif a_list[mid] < n:
            first = mid + 1
        else:
            last = mid - 1 #⭐
    return False


x1 = [1,3,5,7,9,11,13]
a = 11
b = 2

print(binary_search(x1,a))
print(binary_search(x1,b))

👉 실행화면

True
False

파이썬의 bisect_left를 활용한 알고리즘

from bisect import bisect_left
bisect_left(리스트,목표): 반환 값 = 존재하면 있었을 인덱스

from bisect import bisect_left

def binary_search_bisect(a_list,n):
    index = bisect_left(a_list,n)
    if a_list[index] == n:
        return True
    return False

print(binary_search_bisect(x1,a))
print(binary_search_bisect(x1,b))

👉 실행화면

True
False