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

 

1. 선형 탐색 ( Linear Search )

 

소요 시간 : O(n)

리스트의 길이에 비례하는 시간이 소요됩니다.

def solution(L, x):
    for i in range(len(L)):
        if x == L[i]:
            return i
    return -1

L1 = [3,5,2,8,6,1,7]
x = 2
y = 7

print(solution(L1, x))
print(solution(L1, y))

 

 

 

 

2. 이진 탐색 ( Binary Search )

 

소요 시간 : O(log n)

한 번 비교가 일어날 때마다 탐색 대상 데이터를 반씩 줄입니다.

 ( devide & conquer )

정렬된 리스트에서 탐색하는 경우에만 사용 가능

def solution(L,x):
    upper = len(L) - 1
    lower = 0
    while upper >= lower:
        mid = (upper + lower) // 2
        if x == L[mid]:
            return mid
        elif x < L[mid]:
            upper = mid - 1
        else:
            lower = mid + 1
    return -1

L1 = [1,3,5,7,9,11]
x1 = 3
x2 = 7
print(solution(L1, x1))
print(solution(L1, x2))