[Python] 검색 알고리즘 - 선형 검색

안녕하세요, 메이플입니다!

한동안 바쁜 일이 모두 끝나서 오랜만에 포스팅하러 돌아왔습니다 ㅎㅎ

1일 1포스팅을 목표로 블로그를 꾸려나가볼려고요.

아자아자 화이팅!

---

Python 언어로 선형 검색을 구현하기 앞서 먼저 검색에 대해서 간단하게 먼저 설명해보겠습니다.

검색은 데이터 중에 우리가 원하는 특정 데이터를 키(Key: 특정 항목)를 통해서 찾는 것이죠.

 

검색의 종류는 다양하게 있지만, 가장 기본적인 선형 검색, 이진 검색, 해시법에 대해서 다룰 생각입니다.

 

선형 검색

이 알고리즘은 배열에서 검색하는 방법 중 가장 기본적인 알고리즘이라고 볼 수 있죠.

선형 검색(Linear Search)는 순차 검색(Sequential Search)라고도 합니다.

이름에서 알 수 있듯이, 직선 모양(=선형)으로 늘어선 배열에서 원하는 키값을 가진 원소를 찾을 때까지 맨 앞으로 스캔하여 순서대로 검색하는 알고리즘 입니다.

 

그림으로 본다면 아래와 같습니다.

이 알고리즘을 아래 코드처럼 파이썬으로 구현할 수 있습니다.

 

(ex1) while문을 이용한 구현

i = 0
while True:
    if i == len(a):
    # Search Failed
    if a[i] == key:
    # Search success
    i += 1

 

(ex2) for문을 이용한 구현

from typing import Any, Sequecec

def seq_search(a: Sequence, key: Any) -> int:
    for i in range(len(a)):
        if a[i] == key:
            #Search success -> return index
            return i
    #Search failed -> return -1
    return -1

---

보초법

선형 검색을 구현할 때, 종료 조건을 확인하는 방법 중에 반복해서 종료 조건을 검사하는 비용을 반으로 줄이는 방법인 보초법(sential method)이 있습니다.

보초법이란 검색하는 배열의 끝에 검색할 값을 추가하는 방법입니다.

 

코드 먼저 보여드리고 설명하겠습니다.

from typing import Any, Sequece
import copy

def seq_search(seq: Sequece, key: Any) -> int:
    a = copy.deepcopy(seq)
    a.append(key)

    i = 0
    while True:
        if a[i] == key:
            break
        i += 1
    return -1 if i == len(seq) else i
    
if __name__ == '__main__':
	num = int(input('Enter the number of elements. : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    ky = int(input('Search value : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('There is no the value.')
        
        print(f'{ky} is x[{idx}].')

seq_search 함수를 보면 먼저 찾고자 하는 값을 새로 생성한 배열 마지막에 추가하는 것을 볼 수 있습니다.

그리고 ex1 에서 구현한 것처럼 while문을 통해서 검색을 한 후, 마지막에 검색해서 찾는 값의 인덱스가 배열의 길이과 같은 경우 -1을 반환하는거죠.