[Algorithm] 검색 알고리즘_2 (선형 검색)

03-2 선형 검색

선형 검색(linear search)

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

선형 검색

선형 검색의 종료 조건

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

---

배열 a에서 검색하는 프로그램 코드

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

• 선형 검색의 종료 조건 1 ··· if i == len(a)가 성립하면 스캔 종료
• 선형 검색의 종료 조건 2 ··· if a[i] == key가 성립하면 스캔 종료

---

실습 3-1 while 문으로 작성한 선형 검색 알고리즘

# 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 += 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)                         # ky와 값이 같은 원소를 x에서 검색

  if idx == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
  else:
    print(f'검색값은 x[{idx}]에 있습니다.')

원소 수를 입력하세요.: 3
x[0]: 2
x[1]: 6
x[2]: 8
검색할 값을 입력하세요.: 2
검색값은 x[0]에 있습니다.

실습 3-2 for 문으로 작성한 선형 검색 알고리즘

# 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          # 검색 성공(인덱스를 반환)
  return -1             # 검색 실패(-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)                         # ky와 값이 같은 원소를 x에서 검색

  if idx == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
  else:
    print(f'검색값은 x[{idx}]에 있습니다.')

원소 수를 입력하세요.: 4
x[0]: 1
x[1]: 5
x[2]: 2
x[3]: 6
검색할 값을 입력하세요.: 2
검색값은 x[2]에 있습니다.

---

다양한 자료형인 시퀀스에서 검색

실습 3C-1 seq_search() 함수를 사용하여 실수 검색하기

# seq_search() 함수를 사용하여 실수 검색하기

from search_while import seq_search

print('실수를 검색합니다.')
print('주의: "End"를 입력하면 종료합니다.')

number = 0
x = []

while True:
  s = input(f'x[{number}]: ')
  if s == 'End':
    break
  x.append(float(s))
  number += 1

ky = float(input('검색할 값을 입력하세요.: '))

idx = seq_search(x, ky)
if idx == -1:
  print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
  print(f'검색값은 x[{idx}]에 있습니다.')

실수를 검색합니다.
주의: "End"를 입력하면 종료합니다.
x[0]: 2
x[1]: 4
x[2]: 7
x[3]: 9
x[4]: 2
x[5]: 3
x[6]: 6
x[7]: End
검색할 값을 입력하세요.: 2
검색값은 x[0]에 있습니다.

실습 3C-2 seq_search() 함수를 사용하여 특정 인덱스 검색하기

# seq_search() 함수를 사용하여 특정 인덱스 검색하기

from search_while import seq_search

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS','AAC','FLAC']

print(f'{t}에서 5.6의 인덱스는 {seq_search(t, 5.6)}입니다.')
print(f'{s}에서 "n"의 인덱스는 {seq_search(s, "n")}입니다.')
print(f'{a}에서 "DTS"의 인덱스는 {seq_search(a, "DTS")}입니다.')

(4, 7, 5.6, 2, 3.14, 1)에서 5.6의 인덱스는 2입니다.
string에서 "n"의 인덱스는 4입니다.
['DTS', 'AAC', 'FLAC']에서 "DTS"의 인덱스는 0입니다.

---

보초법(sentinel method)

검색하고자 하는 키값을 배열의 맨 끝에 저장합니다. 이때 저장하는 값을 보초(sentinel)라고 합니다.

• 그림 a: 2를 검색하려고 준비, a[7]에 보초 2를 추가합니다.
• 그림 b: 5를 검색하려고 준비, a[7]에 보초 5를 추가합니다.

그림 b처럼 찾는 값이 원래 데이터에 존재하지 않아도 a[7]의 보초까지 스캔하는 단계에서 선형검색의 종료조건 2(검색할 값과 같은 원소를 찾았습니까?)가 성립합니다.
따라서 선형 검색의 종료조건 1(검색할 값을 찾지 못하고 배열의 맨 긑을 지나갔습니까?)은 판단할 필요가 없습니다.

이처럼 보초는 반복을 종료하는 판단 횟수를 줄이는 역할을 합니다.

---

실습 3-3 선형 검색 알고리즘(실습 3-1)을 보초법으로 수정

# 선형 검색 알고리즘을 보초법으로 수정

from typing import Any, Sequence
import copy

def seq_search(seq: Sequence, key: Any) -> int:
  """시퀀스 seq에서 key와 일치하는 원소를 선형 검색(보초법)"""
  a = copy.deepcopy(seq) # seq를 복사
  a.append(key) # 보초 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) # 키 ky값과 같은 원소를 x에서 검색

  if idx == -1:
    print('검색값을 갖는 원소가 존재하지 않습니다.')
  else:
    print(f'검색값은 x[{idx}]에 있습니다.')

원소 수를 입력하세요.: 5
x[0]: 2
x[1]: 4
x[2]: 6
x[3]: 8
x[4]: 12
검색할 값을 입력하세요: 4
검색값은 x[1]에 있습니다.

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B2%80%EC%83%89%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습