이진탐색 안쓰고 내맘대로 풀려다가 시간초과로 실패당해서 강제로 외우는 이진탐색 알고리즘

---

이진탐색(Binary Search) 알고리즘

1. 정의

이진탐색(Binary Search)은 정렬된 배열 안에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘

2. 구현 방법

1. 리스트 정렬 후 시작점(start)과 끝점(end), 중간점(mid)을 설정
2. 중간점의 값과 찾고자 하는 값을 비교, 만약 중간점의 값이 찾고자 하는 값과 같다면 탐색 종료
   2-1) 중간점의 값이 찾고자 하는 값보다 작다면, 시작점을 중간점 + 1로 설정
   2-2) 중간점의 값이 찾고자 하는 값보다 크다면, 끝점을 중간점 - 1로 설정
3. 2번 과정을 반복

3. 예제 코드

이진탐색 알고리즘을 이용하여 정렬된 리스트에서 특정 값을 찾는 예제 코드

def binary_search(lst, target):
    start = 0
    end = len(lst) - 1

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

    return -1

4. 시간 복잡도

이진탐색 알고리즘은 매번 탐색 범위를 절반으로 줄여나가기 때문에, 최악의 경우에도 O(logN)의 시간 복잡도를 가짐

---

BOJ: Q1920 - 수 찾기 [ 실버 4 ]

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2³¹ 보다 크거나 같고 2³¹보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제

입력

5
4 1 5 2 3
5
1 3 7 9 5

출력

1
1
0
0
1

코드

내가 작성한 답

import sys
input=sys.stdin.readline

input()
lst1 = list(map(int, input().split()))
input()
lst2 = list(map(int, input().split()))

for i in lst2:
    if i in lst1:
        print("1")
    else:
        print("0")

쩝 ..
문제에서 의도한 답은 이분탐색이었다

이진탐색으로 구현하는 방법

# 입력
N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))
A.sort()			# A 정렬

# arr의 각 원소별로 이분탐색
for num in arr:
    lt, rt = 0, N - 1		# lt는 맨 앞, rt는 맨 뒤
    isExist = False		# 찾음 여부

    # 이분탐색 시작
    while lt <= rt:		# lt가 rt보다 커지면 반복문 탈출
        mid = (lt + rt) // 2	# mid는 lt와 rt의 중간값
        if num == A[mid]:	# num(목표값)이 A[mid]값과 같다면 (목표값 존재여부를 알았다면)
            isExist = True	# isExist True 변경
            print(1)		# 1 출력
            break		# 반복문 탈출
        elif num > A[mid]:	# A[mid]가 num보다 작으면
            lt = mid + 1	# lt를 높임
        else:			# A[mid]가 num보다 크다면
            rt = mid - 1	# rt를 낮춤

    if not isExist:		# 찾지 못한 경우
        print(0)		# 0 출력

파이썬 bisect 라이브러리를 이용해서 구현하는 방법

📍 bisect(리스트, 항목) 함수는 항목을 리스트에 넣었을 때 삽입되는 인덱스를 반환

import sys
import bisect
input = sys.stdin.readline

n = int(input())
lst1 = list(map(int,input().split()))
m = int(input())
lst2 = list(map(int,input().split()))
lst1.sort()

for i in lst2:
  if lst1[bisect.bisect(lst1,i)-1]==i : # 항목을 리스트에 넣을 때 넣어지는 자리에서 바로 왼쪽에 있는 것이 해당 숫자와 같은지 확인
    print(1) # 같으면 리스트 내에 해당 숫자가 있는 것이므로 1 반환
  else:
    print(0)

📍 bisect_right와 bisect_left를 이용하는 방법

import sys
from bisect import bisect_right, bisect_left
input = sys.stdin.readline
n = int(input())
a=list(map(int,input().split()))
m = int(input())
b=list(map(int,input().split()))
a.sort()
for x in b:
    right_index = bisect_right(a, x) # 정렬된 array에서 x가 위치하게될 오른쪽 인덱스(왼쪽값보다 크지만 오른쪽 값보다 작은 지점의 인덱스)
    left_index = bisect_left(a, x) # 정렬된 array에서 x가 위치하게될 왼쪽 인덱스(왼쪽값보다 크지만 오른쪽 값보다 작은 지점의 인덱스)
    if right_index > left_index: # right_index와 left_index가 차이가 난다면 해당 숫자가 존재하는 것이기에 1을 출력
        print(1)
    else: # right_index와 left_index가 차이가 난다면 해당 숫자가 업는 것이기에 0을 출력
        print(0)