백준 1920 수 찾기

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

1920번: 수 찾기

📌 해결순서

이분탐색을 활용하는 문제중 가장 기본적인 문제라고 할 수 있다.

일단, 이분탐색은 데이터가 정렬 되어 있다고 가정하고 탐색을 시작한다.

다음과 같은 배열에서 2를 찾는 과정을 생각해보자

4

1

5

2

3

배열을 정렬 해준다,

1

2

3

4

5

1. 찾는 데이터가 배열에 있는 경우

target : 2

start : 0 / end : 4

 

비교 1. mid = (0 + 4) // 2 = 2

target = 2 < arr[mid] = 3 이기 때문에 mid 보다 뒤의 배열을 확인 할 필요가 없다. 배열은 이미 정렬되어 있고 배열의 중간값보다 뒤에 있는 값들은 target 값보다 클거기 때문에 비교하지 않고 시간복잡도를 줄인다.

따라서, end = mid - 1 = 1

 

비교2. mid = (0 + 1) // 2 = 0

target = 2 > arr[mid]  = 1 이기 때문에 mid 보다 앞의 배열을 확인 할 필요가 없다.

따라서, start = mid + 1 = 1

 

비교3. mid = (1 + 1) // 2 = 1

target = 2 == arr[mid] =2

따라서 목표값의 인덱스가 mid 인 1 임을 알수 있다.

 

2. 찾는 데이터가 배열에 없는 경우

target : 6

start : 0 / end : 4

 

비교 1.  mid = (0 + 4) // 2 = 2

target = 6 > arr[mid]  = 3

start = mid + 1 = 3

 

비교 2. mid = (3 + 4) // 2 = 3

target = 6 > arr[mid]  =  4

start = mid + 1 = 4

 

비교 3. mid = (4 + 4) // 2 = 4

target = 6 > arr[mid]  =  5

 

start = mid + 1 = 5 

start 인덱스가 end 인덱스 보다 크기 때문에 더이상의 탐색을 할 수가 없다. 따라서 찾는 값이 배열에 없음을 알수 있다.

반대의 경우,

예를 들어 찾는 값이 -1 이라고 생각하면 end 인덱스 값이 계속 줄어들다가 -1 이 되기 때문에 start 인덱스보다 작아지게 된다.

 

📌 코드

import sys
input = sys.stdin.readline


def bi_search(start, end, target):
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] == target:
            return 1
        elif lst[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0


n = int(input())
lst = list(map(int, input().split()))
lst.sort()
m = int(input())
search_lst = list(map(int, input().split()))

for num in search_lst:
    result = bi_search(0, n - 1, num)
    print(result)