[Binary Search] 구현 - python

Binary Search?

특정 숫자를 찾는 Search(탐색) 알고리즘
정렬되어 있는 숫자들 사이에서 '특정 숫자'를 찾을 때 활용된다.
기본 알고리즘은, 정렬된 숫자 사이에서 중간값과 계속해서 비교하며
왼쪽, 오른쪽 두 범위로 나누어(Binary) 탐색(Search) 하는 것이다!

-> 정렬된 숫자들 간에 비교를 하기 때문에 O(logN)의 시간 복잡도를 가진다.
-> 정렬되어 들어오는 경우, 숫자 찾기를 많이 해야하는 경우 효율적으로 활용된다.

Binary Search 구현

1) 재귀적 구현
2) 비재귀적 구현
-> 두 가지 방법을 통해 구현을 할 수 있다.

Binary Search의 재귀적 구현

import sys
n,q = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
question = list(map(int, sys.stdin.readline().split()))

def binarySearch(arr, s, e, value):
  if s>e:
    return False
  elif s==e:
    if arr[s] == value:
      return True
    else:
      return False
  mid = (s+e)//2
  if arr[mid] == value: return True
  elif arr[mid]<value:
    return binarySearch(arr, mid+1,e,value)
  else:
    return binarySearch(arr, s,mid-1, value)

for q in question:
  if binarySearch(numbers,0, n-1,q) == True:
    print('YES')
  else:
    print('NO')

Binary Search의 비재귀적 구현

import sys
def binarySearch(arr, myStart, myEnd, value):
  start = end = mid = 0
  if arr[myStart]>value:
    return -1
  if arr[myEnd]<value:
    return -1
  start = myStart
  end = myEnd
  
  while(end-start>1):
    mid = (start+end)//2
    if arr[mid] == value:
      return mid
    elif arr[mid]<value:
      start = mid
    else:
      end = mid
  return -1
n,m = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
questions = list(map(int, sys.stdin.readline().split()))

for q in questions:
  idx = binarySearch(numbers, 0, n-1, q)
  if idx>-1:
    print('YES')
  else:
    print('NO')

-> while 문 내부에서 start, end 변수가 명확하게 하는 역할을 정의하는 것이 중요하다.
-> start : 찾고자 하는 값보다 작은 값
-> end : 찾고자 하는 값보다 큰 값