알고리즘 - 선형 검색

선형검색은 배열에서 검색하는 방법 중 가장 기본적인 알고리즘입니다.

 

6

4

3

2

1

5

8

9

 

이렇게 직선으로 늘어선 배열에서 검색할 때,

원하는 키 값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다.

 

 

선형검색 코드

from typing import Any, Sequence

def line_search(x:Sequence, key:Any) -> int:
    i = 0
    while True:
        if i == len(x):
            return -1
        if x[i] == key:
            return i
        i += 1
    # 검색한 원소의 값이 있으면 인덱스 값 i 리턴, i가 x의 크기와 같으면 -1 리턴


print('-----선형검색-----')

num = int(input('원소의 수를 입력하세요.: '))

x = [None] * num    # 원소 수가 num인 배열을 만들어준다.

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

ky = int(input('검색할 원소의 값을 입력해주세요.: '))

result = line_search(x, ky)

if result == -1:
    print('검색한 원소의 값이 없습니다.')
else:
    print(f'검색한 원소는 x[{result}]에 있습니다.')     

 

결과창

값이 있을 때

 

 

값이 없을 때

 

---

보초법

선형 검색은 반복할 때마다 값이 있을 때와 없을 때, 두 가지의 종료 조건을 체크합니다.

단순 판단이지만 과정을 반복하면 종료 조건 검사 비용이 커지기 때문에 사용하는 방법이 보초법입니다.

 

1

3

2

8

 

위와 같은 배열이 있을 때 사용자가 찾는 원소 값이 5일 경우에 아래와 같이 배열 끝에 5를 넣어주는 것입니다.

1

3

2

8

5

 

보초법 코드

from typing import Any, Sequence
import copy

def line_search(x:Sequence, key:Any) -> int:
    a = copy.deepcopy(x)  # x를 복사해 배열 a를 만들어줍니다.
    a.append(key)   # a 끝에 key 값을 넣어줍니다.

    for i in range(len(a)):
        if a[i] == key:
            break
    return -1 if i == len(x) else i     
    # i 값이 x의 크기와 같으면 보초로 넣어준 key을 찾은 것이기 때문에 -1 리턴


print('-----보초법-----')

num = int(input('원소의 수를 입력하세요.: '))

x = [None] * num    # 원소 수가 num인 배열을 만들어준다.

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

ky = int(input('검색할 원소의 값을 입력해주세요.: '))

result = line_search(x, ky)

if result == -1:
    print('검색한 원소의 값이 없습니다.')
else:
    print(f'검색한 원소는 x[{result}]에 있습니다.')     

 

 

결과창

 

값이 있을 때

 

 

값이 없을 때