[CS] 이진 탐색(Binary Search)

정렬된 수열에서 특정 수를 찾고자 할 때 사용되는 탐색 알고리즘.

학부 시간에 가장 첫번째로 배우는 탐색 알고리즘이 아닌가 한다.

수행원리상 이 알고리즘을 사용하기 위해선 오름차순으로 배열이 정렬되어 있어야 한다.

 

일반적으로 배열을 전부 순차적으로 탐색하는 방식보다 훨씬 효율적인 방식이다.

이진 탐색이라는 이름과 같이 배열을 반으로 쪼개어 수행한다.

간결한 코드이지만, 꽤나 훌륭한 성능을 보여준다.

 

수행 방식은 다음과 같다.

1.배열의 시작을 left, 배열의 마지막을 right으로 정한다.

2.left와 right의 중간 점을 mid로 정한다.

3.mid로 정한 값이 찾으려는 수보다 크다면 right을 mid-1로 정하고,

  mid로 정한 값이 찾으려는 수보다 작으면 left를 mid+1로 정한다.

4.위 과정을 right < left가 될 때까지 반복한다.

5.mid를 반환한다.

 

import sys
import time

import math

def binarysearch(entries,target):
  left = 1
  right = len(entries)
  mid = 0
  while left<=right:
    mid = math.floor((left+right)/2)
    if entries[mid-1] == target:
      break
    elif entries[mid-1] <  target:
      left = mid+1
    else:
      right = mid -1
  if entries[mid-1] == target:
  	return 1
  else:
  	return 0



n = int(input())
entries = input().split()
entries = list(map(int,entries))


m = int(input())
tofind = input().split()
tofind = list(map(int,tofind))

for x in tofind:
	print(binarysearch(entries,x))
			

작성한 코드이다.