[ALGORITHM] 2. 선형 탐색(Linear Search), 이진탐색(Binary Search)

✅  선형 탐색(Linear Search)

리스트의 맨 처음 원소부터 차례대로 하나씩 검사하여 그 값이 원하는 원소인지 확인하는 알고리즘이다. 원하는 원소를 찾으면 해당 인덱스를 리턴하고 끝까지 검사했는데도 못 찾으면 -1을 리턴한다.

def seqsearch(nbrs, tgt):
    for i in range(0, len(nbrs)):
        if (tgt == nbrs[i]): 
            return i
    return -1

알고리즘을 실행하는데 걸리는 시간은 원소 수에 비례하고 최악의 경우는 찾는 원소가 없는 경우이다. 보통 시간 복잡도를 O(n)으로 표시한다.

 

 

✅  이진탐색(Binary Search)

탐색 범위의 중간 위치의 값을 원하는 원소 값과 비교한다. 중간 위치의 값이 원하는 원소 값보다 더 작으면 중간 위치 오른쪽을 탐색 범위로 지정하고, 중간 위치의 값이 원하는 원소 값보다 더 크면 중간 위치 왼쪽을 탐색 범위로 지정한다. 이 과정을 탐색 범위가 남아 있을 때까지 반복한다.

lower = 0
upper = len(numbers) - 1 
idx = -1
while (lower <= upper):
    middle = int((lower + upper) // 2)
    if numbers[middle] == target :
        idx = middle
        break
    elif numbers[middle] < target :
        lower = middle + 1
	else:
        upper = middle - 1

주어진 데이터가 이미 정렬되어 있는 경우 선형 탐색보다 빠른 속도로 탐색이 가능하다. 이진 탐색의 시간 복잡도는 O(logn)으로 표시한다.