[Algorithm] 검색의 종류 : 순차 검색, 이진 탐색

TOC

• 검색
• 순차 검색(Sequential Search)
  • 정렬되어 있지 않은 경우
  • 정렬되어 있는 경우
• 이진 검색(Binary Search)
  • 검색 과정
  • 구현
  • 재귀함수 이용

검색

• 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
• 목적하는 탐색 키를 가진 항목을 찾는 것
• (탐색 키 : 자료를 구별하여 인식할 수 있는 키)

순차 검색(Sequential Search)

• 일렬로 되어 있는 자료를 순서대로 검색하는 방법
• 가장 간단하고 직관적
• 순차구조로 구현된 자료구조(배열, 연결 리스트 등)에서 유용
• 알고리즘이 단순하여 구현이 쉬움
• but, 검색 대상의 수가 많은 경우 수행시간 급증 → 비효율적

정렬되어 있지 않은 경우

• 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 검색
• 키 값이 동일한 원소를 찾으면 그 원소의 인덱스 반환
• 자료구조의 마지막까지 찾지 못하면 검색 실패

찾고자 하는 원소의 순서에 따라 비교횟수 결정

• 첫 번째 원소를 찾을 때는 1번 비교, 두 번째 원소를 찾을 때는 2번 비교
• 정렬되지 않은 자료에서의 순차 검색의 평균 비교 횟수 : (1/n)*(1+2+3+...+n) = (n+1)/2
• 시간 복잡도 : O(n)

• 구현 예

def sequentialSearch(a, n, key):
    i = 0
    while i<n and a[i]!=key:   # i<n 을 먼저 해야 IndexError가 안 남!!
        i += 1
    if i<n:
      return i
    else:
      return -1

정렬되어 있는 경우

• 자료가 오름차순 정렬된 상태에서 검색을 실시한다고 가정
• 순차적으로 검색하면서 키 값을 비교
• 원소 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 뜻 → 검색 종료

찾고자 하는 원소의 순서에 따라 비교횟수 결정

• 검색 실패를 반환하는 경우 평균 비교횟수가 절반 수준
• 시간 복잡도 : O(n)

• 구현 예

def sequentialSearch(a, n, key):
    i = 0
    while i<n and a[i]<key:
        i += 1
    if i<n and a[i]==key:  # i의 인덱스가 n보다 작고, 검색 값이 key와 같다면
      return i
    else:
      return -1

이진 검색(Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교
• 다음 검색의 위치를 결정하고 검색을 계속 진행
• 검색 범위를 반으로 줄여가면서 빠르게 검색
• 시간복잡도 : O(logn)

주의📢 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다!

검색 과정

• 자료 중앙에 있는 원소를 선택
• 중앙 원소의 값과 찾고자 하는 목표 값 비교
• 크기에 따라 어느 쪽 반을 선택할지 결정 후 인덱스를 조정해서 검색 수행
• 찾을 때까지 반복

구현

• 검색 범위의 시작점과 종료점을 이용해 검색 반복
• 자료의 삽입/삭제 발생 시 배열의 상태를 항상 정렬 상태로 유지하는 작업 필요

def binarySearch(a, N, key):
    start = 0
    end = N-1
    # start가 end보다 커졌다면 탐색 범위를 좁히다가 역전됐다는 말 → 반복 종료
    while start <= end:
        middle = (start+end)//2

        if a[middle] == key:      # 검색 성공
            return True
        elif a[middle] > key:
            end = middle-1        # 작은 구간이니까 종료점이 middle 직전
        else:
            start = middle+1      # 큰 구간이니까 시작점이 middle 직후

    return False                  # 검색 실패

재귀함수 이용

• 재귀함수를 이용해 이진 탐색을 구현해보자.

def binarySearch2(a, low, high, key):
    if low > high:        # 검색 실패
        return False
    else:
        middle = (low+high)//2

        if key == a[middle]:         # 검색 성공
            return True
        elif key < a[middle]:
            return binarySearch2(a, low, middle-1, key)
        else:
            return binarySearch2(a, middle+1, high, key)

하지만 함수 호출에 대한 시간이 더 걸리기 때문에 반복문을 활용하는 것이 시간적으로 더 효율적이다.