백준 1920 수 찾기 - 파이썬

이진 검색 : 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()

M = int(input())
arr = list(map(int, input().split()))
isTrue = True

for key in arr:
  pl = 0
  pr = N - 1
  isTrue = False

  while (pl <= pr):
    pc = (pl + pr) // 2
    if key == A[pc]:
      print(1)
      isTrue = True
      break
    elif (key < A[pc]):
      pr = pc - 1
    else:
      pl = pc + 1
  if not isTrue: print(0)

이진 검색을 활용해서 풀었다

중앙 요소의 인덱스를 while문 안에 넣어서 pl, pr 값에 따라 계속 바뀌도록 해야하는데

while문 밖에두고서는 오류를 찾지 못해 애먹었다 .. ㅎㅎ;

---

이진검색을 하려면 정렬된 배열이 필요하기 때문에 A를 정렬한 후 시작한다.

첫 인덱스(pl)와 마지막 인덱스(pr), 그리고 중앙 인덱스(pc) 값을 잡고,

 

먼저, 중앙 값을 기준으로

1. 중앙 값과 key값이 일치하면 1을 출력,

2. 중앙 값보다 작으면 왼쪽 배열만 검색하면 되기 때문에 pr 끝 값을 pc - 1로 지정하여 왼쪽 배열만 검색하도록

3. 반대로 중앙 값보다 key 값이 크다면 오른쪽 배열만 검색하면 되기 때문에 첫 인덱스(pl) 값을 pc + 1로 지정하여 오른쪽 배열만 검색하도록 한다.

반복문을 통해, pl, pr, pc 값의 범위를 줄여나가면서 일치하는 값을 찾으면 된다.

 

만약 없다면 isTrue 값이 False로 맨 아래 조건문에 걸려 0을 출력하도록 한다.