[백준] 1920 수 찾기와 Python 이진탐색(Binary Search)

#1920 수찾기

1. 시간초과 코드(매우매우 직관적인 코드)

import sys
input = sys.stdin.readline()

n = int(input)
a = list(map(int,input.split()))
m = int(input)
x = list(map(int, input.split()))

for i in range (n):
  if m_arr[i] in n_arr:
    print(1)
  else:
    print(0)

2. 이진탐색 이용(576ms)

import sys

def BinarySearch(a,x):
    start = 0
    end = len(a)-1
    while start<=end:
        mid = (start+end)//2
        if x==a[mid]:
            return 1
        elif x>a[mid]:
            start = mid+1
        else:
            end = mid-1
    return 0

n = int(input())
a = list(map(int,sys.stdin.readline().split()))
a.sort()

m = int(input())
x = list(map(int, sys.stdin.readline().split()))

for i in range (m):
    print(BinarySearch(a,x[i]))

3. 이진탐색 정리할 겸 공부!

 

이진탐색은 큰 배열의 탐색에서는 적합하지 않다. (길이가 길어질수록 시간이 오래걸린다)

정렬된 배열의 중앙값을 기준으로 찾고자 하는 항목이 왼쪽에 있는지 오른쪽에 있는지 판단 후 탐색 범위를 반으로 줄인다.

 

1) a 배열을 정렬한다.

2) start와 end지점을 정해놓고 mid=(start+end )//2를 사용해 중간 지점을 정한다.

3) x[i]값을 a[mid]와 비교하여 일치하면 1을 반환하고 while문 종료,

    x[i] < a[min]라면 왼쪽을 탐색하도록, x[i]>a[mid]라면 오른쪽을 탐색하도록 범위를 좁혀준다. 

4) 위의 단계를 거친 후 x[i]가 a에 존재하지 않으면 0을 return하고 종료

 

크리스마스는 Kermit과 함께 git commit...🤶🏻

 

눈물나는거 아님...