(Python) 리스트의 선형 탐색(linear search)

(Python) 리스트의 선형 탐색 (linear search)¶

---

정렬되지 않은 리스트에서 특정 항목을 찾으려면 어떻게 해야 할까?

이미 정렬된 리스트라면 이진 탐색(binary search)처럼 좀 더 효과적인 탐색 방법을 사용해 볼 수 있겠지만

그렇지 않다면 순차적으로 배열의 모든 항목을 검사해서 원하는 값이 있는지 찾아야 할 것이다.

선형 탐색(linear search)는 가장 기본적인 탐색 방법으로, 위에서 언급한 바와 같이

배열의 모든 항목을 검사해서 원하는 값이 있는지 찾아내는 선형 탐색 기법이다.

In [1]:

# 배열(=array)안에 찾고자 하는 특정 항목(=value)이 있으면 그 index값을 return, 없다면 -1을 return
def linear_search(value, array):
    for i, item in enumerate(array):
        if item == value:
            return i
    return -1

In [2]:

value = 1
array = [5,4,3,2,1,0]

linear_search(value, array)

Out[2]:

4

선형 탐색은 최악의 경우 O(n)의 시간 복잡도를 갖는다.

특정 항목이 끝에 위치해 있거나, 배열에 존재하지 않을 경우 모든 항목을 다 검사해야만 하기 때문이다.

리스트의 index()함수가 실제로 이 알고리즘을 사용하고 있다.

In [3]:

array_1 = [3,4,5,6,7,8]

print(array_1.index(3))
print(array_1.index(4))
print(array_1.index(7))

0
1
4

In [4]:

array_1.index(1) # 리스트 안에 존재하지 않으면 ValueError를 발생시킨다.

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-4-0e6723d293b0> in <module>
----> 1 array_1.index(1) # 리스트 안에 존재하지 않으면 ValueError를 발생시킨다.

ValueError: 1 is not in list