검색 알고리즘 - 선형 검색

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다.

배열 검색의 종류로는 

 

• 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다.
• 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다.
• 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 
  • 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다.
  • 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다.

 

---

선형 검색 linear search

 

가장 기본적인 배열 검색 방법이다. 선형으로 늘어선 배열에서 원하는 Key값을 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다.

 

 

즉, 선형 검색에서 배열 스캔의 종료 조건은 2가지다.

1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 ... 검색 실패

2. 검색할 값과 같은 원소를 찾는 경우 ... 검색 성공

 

# -- 배열 맨 앞부터 순서대로 원소를 스캔하는 선형 검색은 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법이다.

 

<code>

 

# -- while 문으로 작성한 선형 검색 알고리즘
# search_while.py 

from typing import Any, Sequence

from sqlalchemy import true

def seq_search(a: Sequence, key: Any):
    i = 0
    
    while True:
        if i == len(a):
            return -1    # 검색에 실패하여 -1을 반환
        
        if a[i] == key:
            return i    # 검색에 성공하여 현재 검사한 배열의 인덱스를 반환
        
        i += 1
        
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('Enter the Key you want to search for : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('A search Key does not exist.')
    else:
        print(f'The search Key is at x[{idx}].')

 

 

배열의 스캔을 for 문으로 구현하면 코드가 더 짧고 간결해진다. (선형 검색뿐만 아니라 대부분에 적용)

<code>

# -- for 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

from sqlalchemy import true

def seq_search(a: Sequence, key: Any):
    for i in range(len(a)):
        if a[i] == key:
            return i    # 검색 성공(인덱스 반환)
    return -1   # 검색 실패(-1 반환)
        
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('Enter the Key you want to search for : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('A search Key does not exist.')
    else:
        print(f'The search Key is at x[{idx}].')

 

선형 검색은 int 뿐만 아니라 다양한 자료형 검색에 사용할 수 있다.

<open code>

# -- seq_search() 함수를 사용하여 특정 인덱스 검색하기

from search_while import seq_search

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']

print(f'{t}에서 5.6의 인덱스는 {seq_search(t, 5.6)}입니다.')
print(f'{s}에서 "n"의 인덱스는 {seq_search(s, "n")}입니다.')
print(f'{a}에서 "DTS"의 인덱스는 {seq_search(a, "DTS")}입니다.')

 

---

보초법 sentinel method

 

선형 검색은 반복할 때마다 두 가지 종료 조건을 체크하는데, 검색 과정을 반복할수록 비용(cost)을 무시할 수 없다. 보초법은 비용을 반으로 줄이는 방법이다.

 

 

위 사진에서 배열 원소 a[0] ~ a[6]은 기존 데이터이다. 검색하고자 하는 키값을 배열의 끝 a[7]에 저장한다. 저장하는 값을 보초라고 한다. 

그림 b처럼 찾는 값이 존재하지 않아도 선형 검색의 종료 조건 중 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우는 신경 쓰지 않아도 된다.  

 

<code>

# -- while문 선형 검색 알고리즘을 보초법으로 수정

from re import I
from typing import Any, Sequence
import copy

from sympy import sequence

def seq_search(seq: sequence, key: Any):
    a = copy.deepcopy(seq)
    a.append(key)
    
    i = 0
    while True:
        if a[i] == key:
            break   # 검색에 성공하면 while 문 종료
        i += 1
        
    return -1 if i == len(seq) else i    # i값이 len(seq)와 같으면 찾은 것이 보초임으로 실패

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    ky = int(input('검색할 값을 입력하세요 : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
        
    else: 
        print(f'검색값은 x[{idx}]에있습니다.')