[알고리즘 기초] 선형 탐색 ( linear_search)

python 소스로 공부를 해볼거임

 

선형 탐색이란 ? 

앞에서 부터 뒤로 순차적으로 탐색을 하는 알고리즘 ! 

정렬이 되어있다고 해도 앞에서부터 뒤로 탐색을 하는거라서 정렬이 된 경우와 안된경우 모두 O(n)  이다

리스트의 길이에 비례해서 소모시간이 늘어나게 된다

 

가장 쉬운 탐색 코드이지만 리스트의 길이가 길어질수록 비효율적인 탐색방법이다 :-) 

 

파이썬 소스

def linear_search(L,x):
    i =0
    while i<len(L) and L[i] !=x:
        i += 1
    if i < len(L): #탐색에 성공한 경우 
        return i
    else: #탐색에 실패한 경우 
        return -1