[백준] 1920번 수 찾기

💡문제접근

• 이분 탐색의 기초 문제라고 생각하고 접근했다. 일단 이분 탐색을 수행하려면 반드시 정렬이 된 상태여야 하므로 정렬을 수행한 다음 이분 탐색 함수를 사용해서 원소를 탐색했다.

💡코드(메모리 : 45916KB, 시간 : 420ms)

def binary_search(target, data):
    start = 0
    end = len(data) - 1
    while start <= end:
    	# 존재하지 않으면 0을 return
        if start > end:
            return 0
        mid = (start + end) // 2
        # 존재하면 1을 return
        if data[mid] == target:
            return 1
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

N = int(input())
A_li = list(map(int, input().split()))
M = int(input())
B_li = list(map(int, input().split()))

A_li.sort()
for i in B_li:
    if binary_search(i, A_li) == 1:
        print(1)
    else:
        print(0)

💡소요시간 : 5m

📌 이분 탐색

정렬된 자료를 반으로 나누어 탐색하는 방법
자료는 반드시 오름차순으로 정렬된 자료여야 한다.
이분 탐색은 코딩테스트에 자주 출제되는 알고리즘이다. 확실하게 정리하고 공부하자.

📌 이분 탐색 알고리즘을 구현하기 위한 준비

target : 찾고자 하는 값
data : 오름차순으로 정렬된 list로 찾는 값이 저장된 list
start : data의 첫 번째 원소 값의 인덱스
end : data의 마지막 번쨰 원소 값의 인덱스
mid : start와 end의 중간 값의 인덱스

📌 일반적인 이분 탐색 바이너리 서치 구현 코드

while left<=right:
    mid = (left+right)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1

시작 지점의 인덱스 값이 끝 지점의 인덱스 값을 넘어선다면 이분 탐색을 종료한다.