1920번 수 찾기

문제링크 : www.acmicpc.net/problem/1920

1920번: 수 찾기

---

---

<알고리즘>

  1) 숫자배열, 찾고자 하는 수의 배열 입력받기

  2) 처음 주어진 숫자 배열만 정렬(정렬함수가 제일 시간복잡도가 작음) 

  3) 찾고자 하는 수의 배열의 수 만큼 함수를 돌리면서 존재여부 확인

     3-1) 처음 주어진 숫자배열의 경계 밖의 숫자인지 확인 

     3-2) 처음 주어진 숫자배열의 경계의 숫자인지 확인 

     3-3) 위의 경우가 모두 아니라면 재귀함수를 이용해 이분탐색 적용

 

 

이분 탐색 -> 배열의 처음과 끝을 left와 right로 정한 후, target을 mid값((left+right)//2)과 비교해 왼쪽 분할에서 다시 찾을지 오른쪽 분할에서 다시 찾을지를 적용하여 반복

 

+) 참고 : wootool.tistory.com/62

[알고리즘] 이분 탐색

 

 

 

 

메모리 : 44736KB    시간 : 772ms

def isIt(numbers, left, right, mid, wantfind):
    if(numbers[mid]<wantfind):
        if(left==mid or mid == right):
            return 0
        return isIt(numbers,mid,right,(mid+right)//2,wantfind)
    elif(numbers[mid]>wantfind):
        if (left == mid or mid == right):
            return 0
        return isIt(numbers, left,mid,(left+mid)//2,wantfind)
    elif(numbers[mid]==wantfind):
        return 1
import sys
M = int(sys.stdin.readline())
numbers= list(map(int,sys.stdin.readline().split()))
numbers = sorted(numbers)

N = int(sys.stdin.readline())
target = list(map(int,sys.stdin.readline().split()))

#targe N개의 존재여부를 찾음
for i in range(0,N):
    #아예 범위 안에 없는 수인지 확인
    if(numbers[0]>target[i] or numbers[M-1]<target[i]):
        print(0)
    #경계 선 확인
    elif (numbers[0]==target[i] or numbers[M-1]==target[i]):
        print(1)
    #경계선 안 확인
    else:
        print(isIt(numbers, 0,M-1,M//2,target[i]))