수 찾기

❓문제

https://www.acmicpc.net/problem/1920

❗문제 정리

이분 탐색 정리
: 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법

📑코드

n=int(input())
numbers=list(map(int, input().split()))
m=int(input())
find_nums=list(map(int,input().split()))

numbers.sort()
def binary_search(array, target, start, end):
  if start>end:
    return None

  mid=(start+end)//2 #중간점 위치
  
  if array[mid]==target:#찾으려는 값이 중간점과 같은 경우
    return mid#중간점 위치 리턴

  elif array[mid]>target:#중간점이 찾으려는 값보다 큰 경우 중간점 이후는 보지 않음 
    return binary_search(array, target, start, mid-1)
  else:#찾으려는 값이 중간점보다 작은 경우
    return binary_search(array, target, mid+1, end)

for target in find_nums:
  if binary_search(numbers, target, 0, n-1) or binary_search(numbers, target, 0, n-1)==0:
    print(1)
  else:
    print(0)
  

📝코드 설명

n=int(input())
numbers=list(map(int, input().split()))
m=int(input())
find_nums=list(map(int,input().split()))

탐색당할 수들의 개수 n, 탐색당할 수 numbers, 탐색할 수들의 개수m, 탐색할 수 find_nums를 입력받는다.

numbers.sort()

탐색당할 수들을 오름차순으로 정렬

def binary_search(array, target, start, end):
  if start>end:
    return None

  mid=(start+end)//2 #중간점 위치
  
  if array[mid]==target:#찾으려는 값이 중간점과 같은 경우
    return mid#중간점 위치 리턴

  elif array[mid]>target:#중간점이 찾으려는 값보다 큰 경우 중간점 이후는 보지 않음 
    return binary_search(array, target, start, mid-1)
  else:#찾으려는 값이 중간점보다 작은 경우
    return binary_search(array, target, mid+1, end)

이진탐색하는 함수 binary_search 정의.
시작값위치 start, 중간값위치 mid, 끝값위치 end로 설정.
이때, 중간값위치는 (시작값+끝값)//2로 소수점 이하는 버린다.

• if : 중간값이 찾으려는 값과 같은 경우 중간값의 위치 리턴
• elif : 중간값이 찾으려는 값보다 큰 경우 중간값 이후는 볼 필요가 없으므로, 끝값 위치는 중간값의 바로 앞으로 지정하고 다시 이진 탐색 수행.
• else: 중간값이 찾으려는 값보다 작은 경우, 중간값 이 전을 볼 필요 없으므로 시작값 위치를 중간값 바로 뒤의 값으로 설정하고 이진탐색 수행.
• 이진 탐색의 결과는 찾으려는 값의 인덱스!

for target in find_nums:
  if binary_search(numbers, target, 0, n-1) or binary_search(numbers, target, 0, n-1)==0:
    print(1)
  else:
    print(0)

이진 탐색의 결과가 인덱스일경우(0~n-1) 1을 출력
none 일 경우, 0을 출력

🎖제출 결과

💡insight