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

별 의미 없는 사진

✏️ 이진탐색알고리즘의 작동방식

이진탐색은 정렬된 리스트에서 특정 요소를 찾는 알고리즘이다.

• 분할(Devide)

리스트를 중간값을 기준으로 두개의 리스트로 분할한다.

• 정복(Conquer)

- 검색할 숫자 < 중간값 이면 중간값 앞의 리스트에서 검색할 요소를 찾는다.

- 검색할 숫자 > 중간값 이면 중간값 뒤의 리스트에서 검색할 요소를 찾는다.

- 검색할 숫자 == 중간값 이면 값을 리턴한다.

 

✏️ 이진탐색알고리즘 구현 (Python)

재귀적 구현

def BS(array, target, start, end):
  if start>end:
    return None
  mid=(start+end)//2
  if array[mid]==target:
    return mid
  elif array[mid]>target:
    return BS(array,target,start,mid-1)
  else:
    return BS(array,target,mid+1,end)

#n(원소의 개수)와 target(찾는 값)입력 
n, target = list(map(int, input().split()))
# 전체 원소 입력
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result=BS(array, target, 0, n-1)
if result==None:
  print('None')
else:
  print(result)

 

✏️ 이진탐색알고리즘을 이용한 문제 (백준 1920번)

1920번: 수 찾기

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
M=int(input())
target_list=list(map(int, input().split()))

def BS(target, array, start, end):
  if start > end:
    return 0
  mid = (start+end)//2
  if array[mid]==target:
    return 1
  elif array[mid]<target:
    return BS(target, array, mid+1, end)
  else:
    return BS(target, array, start, mid-1)

for target in target_list:
  print(BS(target, A, 0, N-1))