[자료구조] 검색 알고리즘 (선형 검색/ 이진 검색) / Python 파이썬
검색 알고리즘이란?
정렬은 흩어져있는 데이터를 키 값(주민등록번호, 학번 등)을 이용하여 순서대로 열거하는 알고리즘이다.
검색은 데이터(정렬이 안된 데이터 , 정렬이 된 데이터)에서 키 값에 해당되는 데이터를 찾는 알고리즘이다.
검색(Search) :
n 개의 데이터를 검색한다. 가장 간단한 검색 알고리즘은 선형 검색(Sequential Search) 알고리즘이다.
n개의 데이터를 놓고 한 개씩 검색하는 방법이다. 데이터가 정렬이 된 상태에서는 이진 검색(Binary Search) 방법이 더 효율적이다. 이진 검색은 전체 데이터의 중간에 있는 데이터를 비교하면서 찾는 데이터가 앞/뒤 중 어디 있는지 알 수 있다.
선형 검색
선형 검색 알고리즘은 직선 모양으로 늘어선 요소의 배열에서 앞부터 순차적으로 검색을 수행한다.
선형 검색의 종료 조건
- 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 -> 검색 실패
- 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공
배열 원소의 갯수가 n이라면 이 조건을 판단하는 횟수는 평균 n / 2번이다.
배열 a에서 검색하는 프로그램을 다음과 같이 나타낼 수 있다.
i = 0
while True:
if i == len(a):
# 검색 실패
if a[i] == key:
# 검색 성공(찾은 원소의 인덱스는 i)
i += 1for 문으로 작성한 선형 검색 알고리즘
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)으로 줄어든다.
- 리스트의 첫 번째 인덱스와 마지막 인덱스의 값을 합하여 2로 나눈 후, 중간 인덱스로 지정한다.
- 구하고자 하는 숫자(Target)가, 중간 인덱스보다 적은 경우 중간 이후 값은 검색 범위에서 제외한다.
- 구하고자 하는 숫자(Target)가, 중간 인덱스보다 큰 경우 중간 이전 값은 범위에서 제외한다.
예제 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
알고리즘 문제풀이 - 선형검색과 보초법 & 이진탐색 (Python)
1. 선형 검색 선형 검색 알고리즘은 직선 모양으로 늘어선 요소의 배열에서 앞부터 순차적으로 검색을 수행한다. 선형 검색 알고리즘에서 종료 조건은 2가지이다. 1. 배열의 끝 2. 검색할 값을 발
local-dev.tistory.com
[3] do it! 자료구조와 함께 배우는 알고리즘 입문-파이썬 편