[알고리즘] 선형 검색(Linear Search)

선형검색
(Linear Search)

: 선형으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞으로 스캔하여 순서대로 검색하는 알고리즘! (순차검색이라고도 합니다)

해달 gif와 같이, 배열의 원소를 맨 앞부터 순서대로 스캔하여 검색

선형 검색의 종료 조건

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

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

1. while문 활용

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 값이 같은 원소를 선형 검색 (while문)"""
    i = 0 
    
    while True:
        if i == len(a):
            return -1	# 검색 실패 -> -1 
        
        if a[i] == key:
            return i	# 검색 성공 -> i
        i += 1
    
if __name__ == '__main__':
    num = int(input('원소 개수를 입력하세요: '))
    x = [None] * num	# 원소 수가 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}]에 있습니다.')

• 결과같은 아래와 같이 출력됩니다
  

2. for문 활용

from typing import Any, Sequence

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

정말 간결해졌네요..