Study Log

Binary Search

[탐색] 이진탐색( Binary Search ) 알고리즘

  • 시간복잡도 logN
  • 정렬된 자료를 반으로 나누어 탐색
  • 단, 자료는 오름차순 으로 정렬된 자료여야 한다.
  • 퍼포먼스가 좋다

핵심 변수

  • start : 리스트의 첫번째 원소 idx
  • end : 리스트의 마지막 원소 idx
  • mid : (start + end) // 2

Big-O

  • K번 실행시 남은 자료의 개수는 n*(1/2)^k
  • 탐색이 끝나는 시점에 남은자료의 개수는 1 -> n*(1/2)^k = 1
  • 양변에 2^k를 곱하면 n = 2^k -> log2^N = k
  • k의 의미는 실행횟수 따라서 N에 따른 시행횟수는 O(logN) 으로 표기 가능

구현1

def binary_search(target, data):
  data.sort()
  start = 0
  end = len(data)-1
  while start<=end:
    mid = (start+end)//2
    if target == data[mid]:
      return mid
    elif data[mid] < target:
      start = mid +1
    else:
      end = mid-1
  return None

구현2 By Recursion

# data는 오름차순 정렬된 데이터라고 가정
def binary_search(start, end, target, data):
  if start > end:
    return None
  mid = (start+end) // 2
  if data[mid] == target:
    return data[mid]
  elif data[mid] < target:
    start = mid + 1
  else:
    end = mid - 1
  return binary_search(start, end, target, data)
Written by@[HongDongUk]
공부한 것을 소소하게 적는 블로그.

GitHubFacebook