[자료구조] 검색 알고리즘 (선형 검색/ 이진 검색) / Python 파이썬

검색 알고리즘이란?

정렬은 흩어져있는 데이터를 키 값(주민등록번호, 학번 등)을 이용하여 순서대로 열거하는 알고리즘이다.

검색은 데이터(정렬이 안된 데이터 , 정렬이 된 데이터)에서 키 값에 해당되는 데이터를 찾는 알고리즘이다.

 

검색(Search) :

n 개의 데이터를 검색한다. 가장 간단한 검색 알고리즘은 선형 검색(Sequential Search) 알고리즘이다.

n개의 데이터를 놓고 한 개씩 검색하는 방법이다. 데이터가 정렬이 된 상태에서는 이진 검색(Binary Search) 방법이 더 효율적이다. 이진 검색은 전체 데이터의 중간에 있는 데이터를 비교하면서 찾는 데이터가 앞/뒤 중 어디 있는지 알 수 있다.

 

 

---

선형 검색

선형 검색 알고리즘은 직선 모양으로 늘어선 요소의 배열에서 앞부터 순차적으로 검색을 수행한다.

 

선형 검색의 종료 조건

1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 -> 검색 실패
2. 검색할 값과 같은 원소를 찾는 경우                        -> 검색 성공

배열 원소의 갯수가 n이라면 이 조건을 판단하는 횟수는 평균 n / 2번이다.

 

배열 a에서 검색하는 프로그램을 다음과 같이 나타낼 수 있다.

i = 0
while True:
	if i == len(a):
    	# 검색 실패
    if a[i] == key:
    	# 검색 성공(찾은 원소의 인덱스는 i)
    i += 1

---

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

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 값이 같은 원소를 선형 검색(while문)"""
        
    for i in range(len(a)):
        if a[i] == key:
            return i
    return -1

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요: '))   # num값을 입력받음
    x = [None] * num                          # 원소 수가 num인 배열을 생성
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
                  
    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 키 ky를 입력받음
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

 

---

보초법

선형 검색은 반복할 때마다 2가지 종료 조건을 체크한다. 단순한 판단이지만 이 과정을 계속 반복하면 종료 조건을 검사하는 비용을 무시할 수 없다. 이 비용을 반으로 줄이는 방법을 보초법(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
    return -1 if i == len(seq) else i

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요: '))   # num값을 입력받음
    x = [None] * num                          # 원소 수가 num인 배열을 생성
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
                  
    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 키 ky를 입력받음
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

---

이진탐색

이진탐색은 정렬된 리스트를 전제로 하며, 1회 비교를 할 때마다 탐색 범위가 절반(시간복잡도 : logn)으로 줄어든다.

1. 리스트의 첫 번째 인덱스와 마지막 인덱스의 값을 합하여 2로 나눈 후, 중간 인덱스로 지정한다.
2. 구하고자 하는 숫자(Target)가, 중간 인덱스보다 적은 경우 중간 이후 값은 검색 범위에서 제외한다.
3. 구하고자 하는 숫자(Target)가, 중간 인덱스보다 큰 경우 중간 이전 값은 범위에서 제외한다.

 

[출처] [1]

예제 1

target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()
left = 0 
right = length-1

while left<=right:
    mid = (left+right)//2 # 중간 값
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1

 

 

## 이진 검색 알고리즘
from typing import Any, Sequence

def bin_search(a:Sequence, key: Any) -> int:
    pl = 0              # 검색 범위 맨 앞 원소의 인덱스
    pr = len(a) -1      # 검색 범위 맨 끝 원소의 인덱스
    
    while True:
        pc = (pl + pr) // 2
        if a[pc] == key:
            return pc
        elif a[pc] < key:
            pl = pc + 1
        else:
            pr = pc - 1
        if pl > pr:
            break
    return -1

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요: '))
    x = [None] * num
    
    print('배열 데이터를 오름차순으로 입력하세요: ')
    
    x[0] = int(input('x[0]: '))
    
    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            if x[i] >= x[i - 1]:
                break
                
    ky = int(input('검색할 값을 입력하세요.: '))
    
    idx = bin_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

---

REFERENCE

[1] https://velog.io/@madfinger/Binary-Search%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[2] https://local-dev.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-python-%EC%84%A0%ED%98%95%EA%B2%80%EC%83%89%EA%B3%BC-%EB%B3%B4%EC%B4%88%EB%B2%95 

알고리즘 문제풀이 - 선형검색과 보초법 & 이진탐색 (Python)

[3] do it! 자료구조와 함께 배우는 알고리즘 입문-파이썬 편