[알고리즘] Binary Search

순차 탐색

순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

N개의 데이터가 있을 때 차례대로 하나씩 확인

파이썬의 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 함수를 이용할 때도 내부에서 순차 탐색이 수행된다.

데이터의 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인
데이터 개수가 N개일 때 최대 N번의 연산이 필요
시간 복잡도는 O(N)

def sequential_search(array, target):
  for i in range(len(array)): #각 원소를 하나씩 확인
    if array[i] == target: #각 원소와 찾고자 하는 값 비교
      return i #찾고자 하는 값의 인덱스 반환

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

index = sequential_search(array, 9)

print('타겟 값의 인덱스 : %d' %index)

이진 탐색

이진 탐색(Binary Search) 알고리즘
배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있는 알고리즘
정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다.

위치를 나타내는 변수 3개를 사용
탐색할 범위의 시작점, 끝점, 중간점

찾으려는 데이터의 중간점(Middle)위치에 있는 데이터를 반복적으로 비교

한 단계를 거칠 때마다 확인하는 원소가 평균적으로 절반씩 줄어든다.
시간 복잡도는 O(logN)

재귀 함수를 이용한 이진 탐색

def binary_search(array, target, start, end):
  if start > end:
    return None #시작점의 위치가 끝점의 위치를 벗어 날 때

  mid = (start + end)//2 #중간점의 위치

  if target == array[mid]: #타겟 값을 찾은 경우, 타겟 값의 위치가 중간점일 때
    return mid #중간점의 위치 반환
  
  elif target < array[mid]: #타겟 값이 중간점의 값보다 작을 때
    return binary_search(array, target, start, mid-1) #중간점의 왼쪽을 탐색
  
  else: #타겟 값이 중간점의 값보다 클 때
    return binary_search(array, target, mid+1, end) #중간점의 오른쪽을 탐색
  
array = [1, 3, 5, 7, 9, 11, 13, 15] #정렬된 리스트에 대한 탐색이 가능
target = 3

index = binary_search(array, target, 0, len(array)-1)

반복문을 이용한 이진 탐색

def binary_search2(array, target, start, end):
  while start <= end:
    mid = (start + end)//2 #중간점의 위치

    if target == array[mid]: #타겟 값을 찾은 경우, 타겟 값의 위치가 중간점일 때
      return mid
    
    elif target < array[mid]: #타겟 값이 중간점의 값보다 작을 때
      end = mid - 1 #중간점의 왼쪽을 탐색

    else:  #타겟 값이 중간점의 값보다 클 때
      start = mid + 1 #중간점의 오른쪽을 탐색

  return None  #시작점의 위치가 끝점의 위치를 벗어 날 때

array2 = [2, 4, 6, 8, 10, 12, 14, 16] #정렬된 리스트에 대한 탐색이 가능
target2 = 14

index2 = binary_search2(array2, target2, 0, len(array)-1)

if index2 == None:
  print('존재하지 않습니다.')
else:
  print('타겟 값 : {}, 인덱스 : {}'.format(target2, index2))

이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색으 가정하는 경우가 많다.
탐색 범위가 2,000만을 넘는다면 이진 탐색으로 접근 권장
처리한 데이터의 개수나 값이 1,000만 단위 이상을 넘을 경우 O(logN) 알고리즘 고려

참고

나동빈(2020).이것이 취업을 위한 코딩 테스트다 with 파이썬.한빛미디어