[알고리즘] 선형 검색 (linear search), 보초법(sentinel method)에 대하여

선형 검색?

선형의 배열에서 검색하는 경우, 원하는 키 값을 가진 원소를 찾을 때 까지 맨 앞부터 스캔하여 차례차례 검색하는 알고리즘이다. 아래와 같이 앞에서부터 값을 비교하면서 검색을 진행한다.

이 때, 만약 2가 아니라 8을 검색하려고 하였다면 검색이 실패하게 된다.

 

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

• 검색할 값과 일치하는 원소를 찾은 경우 (성공)
• 검색할 값을 찾지 못하고 배열의 맨 끝에 도달한 경우 (실패)

 

선형 검색의 구현 with 파이썬

def linearSearch(arr, key):
    i = 0
    while True:
        if i == len(arr):
            return -1
        if arr[i] == key:
            return i
        i += 1

while문으로 구현

 

def linearSearch(arr, key):
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    else:
        return -1

for문으로 구현

 

보초법이란?

앞의 기존 선형 검색 과정에서 종료 조건은 아래와 같았다.

• 검색할 값과 일치하는 원소를 찾은 경우 (성공)
• 검색할 값을 찾지 못하고 배열의 맨 끝에 도달한 경우 (실패)

이 때, 종료 조건은 2가지로 검사 비용이 들게 된다.

이러한 검사 비용을 줄이기 위하여 등장한 것이 바로 보초법이다.

 

보초법은 검색 대상 배열 맨 뒤에 검색하고자 하는 키 값을 추가하는 것이다.

그리고 종료 조건을 다음과 같은 한 가지로 줄이게 된다.

• 검색할 값과 일치하는 원소를 찾은 경우

검색 대상 배열에 키와 일치하는 값이 존재하지 않았더라도, 보초법을 통해 배열의 맨 뒤에 키 값이 추가되었으므로 알고리즘은 종료되게 된다.

 

위 그림과 같이 검색 대상 배열이 [7, 4, 1, 2, 6, 2, 9] 이었다면, 배열의 마지막에 검색 키인 2를 추가한다.

이후 검색 키와 일치하는 값을 찾을 때 까지 검색을 진행한다.

 

만약, 기존의 배열에 키 값이 존재하지 않았다고 하더라도, 알고리즘은 종료된다.

위와 같이 기존에 5는 존재하지 않았지만, 배열의 맨 뒤에 5를 추가함으로써 알고리즘이 종료될 수 있다.

 

보초법을 적용한 선형 검색 알고리즘 구현

import copy

def linearSearch(arr, key):
    a = copy.deepcopy(arr)
    a.append(key)       # 보초 key 추가

    i = 0
    while True:
        if a[i] == key:
            break
        i += 1
    
    if i == len(arr):
        return -1
    else:
        return i

---

다음의 책을 참고하였습니다.

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - 예스24