[파이썬] 자료찾기 알고리즘 - 검색 방법(순차 검색, 이진 검색)

검색 방법(Search)

저장되어 있는 자료 중에서 원하는 항목을 찾는 작업

• 순차 검색 (sequential search)
• 이진 검색 (binary search)

정렬되어 있지 않은 경우의 검색 과정

• 첫 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾음
• 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환
• 자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패
• ex) [4, 9, 2, 7, 21] 에서 7을 검색하는경우
  • 앞에서부터 체크 4≠7 → 9≠7 → 2≠7 ≠ 7 = 7

  def search(a, key):
      x = 0
      n = len(a)
      while x < n and a[x] != key :
          x += 1
      if x<n :
          return x
      else :
          return None
  

반응형

정렬되어 있을 경우의 검색 과정

• 자료를 순차적으로 검색하면서 키 값과 비교하며 찾음
• 키 값이 검색 대상의 키 값보다 클 경우 원소가 없으므로 검색종료
• [2, 4, 7, 9, 21] 에서 6을 검색하는경우
  • 앞에서부터 체크 2 ≠ 6 → 4 ≠ 6 → 7 ≠ 6 (이후의 값은 전부 6보다 큰 값이니 존재하지 않으므로 검색 종료)

  def search(a, key):
      x = 0
      n = len(a)
      while x < n and a[x] < key :
          x += 1
      if x<n and a[x] == key :
          return x
      else :
          return None
  

이진 검색(Binary Search)

자료의 가운데의 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 진행하는 방법

검색과정

• 중앙에 있는 원소 선택
• 중앙 원소의 값과 목표 값 비교
• 목표 값이 원소 값보다 작으면 자료의 왼쪽 반에 대해 새로 검색 수행, 크다면 오른쪽 반에 대해서 새로 검색 수행
• 위의 과정을 반복
• [2, 4, 5, 7, 9, 16, 21] 에서 5를 찾는 경우
  • 중앙값인 7을 기준으로 7 < 4 이므로 왼쪽에서 검색 → 왼쪽에서 중앙 값인 4를 기준으로 오른쪽에서 검색으로 5를 찾음

특징

• 자료가 꼭 정렬되어있는 상태여야 한다
• 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요

def search(a, key):
    start = 0
    end = len(a)-1
    while start <= end :
        middle = (start + end) // 2
        if a[middle] == key : # 키 값을 찾을 경우
            return True
        elif a[middle] > key : # 키 값보다 클 경우 (오른쪽에서 탐색)
            end = middle -1
        else : # 키 값보다 작을 경우 (왼쪽에서 탐색)
            start = middle +1
    return False