7. 선형 검색

---

 

 

1. 검색 알고리즘 (Search Algorithm)

검색 알고리즘이란, 데이터 집합에서 원하는 값을 지닌 원소를 찾아내는 알고리즘 또는 어떤 조건을 만족하는 데이터를 찾아내는 알고리즘을 말한다.

 

1.1) 키(Key)

데이터의 일부로 검색 조건에서 주목하는 항목이다.

데이터가 정수 값이나 문자열일 경우, 데이터 값 그 자체가 키가 되기도 한다.

• 국적이 한국인인 사람을 찾는다. (국적: 키값과 일치하도록 지정)
• 나이가 21세 이상 27세 미만인 사람을 찾는다. (나이: 키값의 구간을 지정)
• 이름에 '김'자가 들어산 사람을 찾는다. (문자: 키값에 가깝도록 지정)

검색 조건은 1개만 지정할 수도 있고, 논리곱이나 논리합을 사용해 복합적으로 지정할 수 있다.

 

---

 

2. 검색의 종류

검색 알고리즘의 종류는 다음과 같다.

• 배열 검색
• 연결 리스트 검색
• 이진 검색 트리 검색

 

2.1) 배열 검색법의 종류

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

 

---

 

3. 검색 알고리즘 선택 요령

검색 속도가 중요하면 계산 시간이 짧은 알고리즘을 선택하는 것이 유리하다.

검색 외에 데이터 추가 및 삭제 작업을 자주 수행해야 한다면, 검색 이외에 작업에 들어가는 추가 비용을 고려하여 선택해야 한다.

용도, 목적, 실행 속도, 자료구조 등을 종합적으로 검토해서 선택해야 한다.

 

---

 

4. 선형 검색법 (Linear Search)

선형(직선 모양)으로 늘어선 배열에서 검색을 진행할 때, 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색을 진행한다.

원소 값이 정렬되지 않은 배열에서 검색할 때 사용할 수 있는 유일한 알고리즘이다.

선형 검색의 종료 조건은 다음과 같다.

• 검색할 값을 찾지 못하고 배열의 끝을 넘어설 경우, 검색 실패
• 검색할 값과 동일한 원소를 찾은 경우, 검색 성공

 

---

 

5. 배열 a에서 검색하는 알고리즘

배열 a에서 사용자가 원하는 값을 찾아내는 알고리즘을 구현해보자.

선형 검색의 종료 조건은 다음과 같다.

i = 0

while (True) :
    if (i == len(a)) :
        ## Fail
    if (a[i] == key) :
        ## Success
        
    i += 1

if (i == len(a)) 조건이 성립할 경우, 검색 실패

if (a[i] == key) 조건이 성립할 경우, 검색 성공

 

5.1) while 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence


def seq_search(a: Sequence, key: Any) -> int :
    i = 0
    
    while (True) :
        if (i == len(a)) :
            return -1
            
        if (a[i] == key) :
            return i
        
        i += 1
        
        
        
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}]')

seq_search() 함수는 시퀀스 a에서 값이 key인 원소를 선형 검색하는 함수이다.

맨 처음 찾은 원소의 인덱스를 반환한다.

검색에 실패하면 -1을 반환한다.

 

5.2) for 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence


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

인덱스와 배열의 길이를 비교하는 if 문을 생략해서 더 짧고 간결하게 구현하였다.

 

---

 

6. 선형 검색 알고리즘으로 실수 검색하기

from ssearch_while import seq_search


print('실수 검색')
print('END 입력 시 종료')

number = 0
x = []

while True :
    s = input(f"x[{number}]")
    
    if (s == "END") :
        break
    
    x.append(float(s))
    number += 1
    
    
ky = float(input('검색할 값: '))

idx = seq_search(x, ky)

if (idx == -1) :
    print("원소가 존재하지 않음")
else :
    print(f"검색값: x[{idx}]")

 

---

 

7. 선형 검색 알고리즘으로 특정 인덱스 검색하기

from ssearch_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"{t}에서 "DTS"의 인덱스: {seq_search(a, "DTS")}")

임의의 자료형인 시퀀스에서도 검색이 가능하다.

 

---

 

8. 선형 검색의 비용

선형 검색은 반복할 때마다 2가지 종료 조건을 체크해야 한다.

• 검색할 값을 찾지 못하고 배열의 맨 끝을 지난 경우: 검색 실패
• 검색할 값과 같은 원소를 찾은 경우: 검색 성공

종료 조건은 단순 판단이지만, 배열의 크기가 커지면 종료 조건 검사 비용도 커진다.

 

8.1) 보초법 (Sentinel Method)

보초(Sentinel)란, 배열의 맨 끝에 추가한 검색하고자 하는 키 값이다.

검색할 값과 같은 원소인지 여부만을 판단하도록 만들어 맨 끝에 도달했는가에 대한 판단을 생략한다.

종료 조건 판단 비용을 반으로 절감할 수 있다.

from typing import Any, Sequence
import copy


def seq_search(seq: Sequence, key: Any) -> int :
    a = copy.deepcopy(seq)
    a.append(key)
    
    i = 0
    
    while (True) :
        if (a[i] == key) :
            break
        
        i += 1
        
    if (i == len(seq)) :
        return -1
    else :
        return i

종료 조건에 의해 찾은 원소가 배열의 원소인지 보초인지를 판단한다.

 

---

 

---

수고하셨습니다!

---