Search algorithm(검색, 탐색 알고리즘) 1탄 - Linear search(선형탐색)

💗 검색/탐색 알고리즘 :  말그대로 특정 값을 찾는 알고리즘.💗

 

 

(cf) 알고리즘 성능은 보통 time complexity로 판단하므로

complexity를 개선하기 위한 다양한 시도가 이루어졌다... 

 

 

 

1. Linear Search (선형 탐색)

- 처음부터 순서대로 하나씩 확인하는 방법. 특정 값 찾으면 그 값의 위치(index)를 return함.

- 맨 앞에 있는 값만 찾는다는 단점(?) 존재.

   ex) [1,2,3,2]에서 2를 찾는 경우, 맨 앞의 2만 찾음.

 

 

 

# 직접 코딩
from typing import List, Any           #이건 필수 아님. argument가 뭔기 명시할 때 필요해서 import한 것.
def linear(L:List, val:Any) -> int:
    for i in range(len(L)):
        if L[i] == val:
            return i
    return -1

linear([1,2,3,2],2)  
>> 1

 

 

# Built-in 함수 이용.
x = [1,2,34,5,100]
x.index(34)
>> 2

 

 

→ list.index()의 경우, 파이썬 내장함수이고 C로 코딩해 놓은 거라 파이썬으로 직접 코딩한 경우보다 훨씬 빠름!! 

     (C가 파이썬보다 속도는 훨씬 빠르니까..ㅎㅎ)

 

 

 

 

 

---

cf) 참고할만한 사이트

https://ko.wikipedia.org/wiki/%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

검색 알고리즘 - 위키백과, 우리 모두의 백과사전

https://velog.io/@dlrmsghks7/%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4

탐색 알고리즘을 알아봅시다!!:)