파이썬 배열 선형 검색

선형 검색

_선형 검색이란 직선 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키 값을 가진 원소를 찾을 때 까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다.

 

_선형 검색의 종료 조건은 1. 검색할 값을 찾지 못하고, 배열의 맨 끝을 지나간 경우 -> 검색 실패한체 종료 2. 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공

 

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

 

---

 

선형 검색의 기본 코드는 다음과 같습니다.
_while문 사용

from typing import Any, Sequence

def seq_search(a: Sequence, Key: Any) -> int:
    # 시퀀스 a에서 Key와 값이 같은 원소를 반복문을 통해서 선형 검색

    i = 0

    while True:
        # 끝까지 같은 원소가 없을 경우
        if i == len(a):
            return -1        
        # Key와 값이 같은 원소를 발견했을 때 원소의 인덱스 리턴    
        if a[i] == Key:
            return i        
        i +=1

 

---

 

Devide & Conquer

        # 끝까지 같은 원소가 없을 경우
        if i == len(a):
            return -1

_선형 검색의 종료 조건인

 1. 검색할 값을 찾지 못하고, 배열의 맨 끝을 지나간 경우 -> 검색 실패한체 종료

 

        # Key와 값이 같은 원소를 발견했을 때 원소의 인덱스 리턴    
        if a[i] == Key:
            return i

_선형 검색의 종료 조건인

 2. 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공

 

---

 

_for문 사용

from typing import Any, Sequence

def seq_search(a: Sequence, Key: Any) -> int:
    # 시퀀스 a에서 Key와 값이 같은 원소를 반복문을 통해서 선형 검색

    for i in range(len(a)):
        if a[i] == Key:
            return i
    return -1

 

---

 

 

선형 검색은 최악의 경우의 시간 복잡도가 너무 높습니다ㅜㅜ

 

그러기에 우리는 선형 검색의 시간을 절반으로 줄여줄 보초법에 대해 알아보겠습니다.

 

 

_보초법이란 검색하고자 하는 키값을 배열의 맨 마지막 원소로 추가해주는 방법을 의미합니다.

이 과정에서 맨 마지막에 추가되는 즉 검색하고자 하는 키값이 보초입니다. 

 

배열 a가 아래와 같을 때 저희는 3이라는 값을 배열 a에서 찾고 싶습니다. 그러니 배열 a에 보초를 추가 해줍시다.

6

7

2

4

5

 

배열 a에 보초 3을 추가해준 모습입니다.

6

7

2

4

5

3

 

이렇게 보초를 추가해주면서 기존 선형 검색의 종료조건 1인

1. 검색할 값을 찾지 못하고, 배열의 맨 끝을 지나간 경우 -> 검색 실패한체 종료

를 거치지 않아도 되었습니다! 그 이유는 모두 알다시피 찾고자 하는 값을 배열에 넣어주었기 때문이죠!!!!

 

 

반복문을 하나 줄이는 것이 시간복잡도를 낮추는데 엄청난 공을 세웁니다!

 

 

_보초법으로 위 코드를 수정한 코드입니다.

from typing import Any, Sequence
import copy

def seq_search(seq: Sequence, Key: Any) -> int:
    # 시퀀스 a에서 Key와 값이 같은 원소를 반복문을 통해서 선형 검색

    a = copy.deepcopy(seq) # 배열을 복사해줍니다!
    a.append(Key) # 마지막에 보초를 추가해줍니다!

    i = 0
    while True:
        if a[i] == Key:
            break
        i += 1
    # 만약 i가 배열의 맨 마지막 원소와 같으면 -1을 반환하고 아니면 i를 반환합니다.
    return -1 if i == len(seq) else i