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

00 개요

• 목표: 코딩테스트 뽀개기!

01 이진탐색 (Binary Search)

1. 이진탐색이란

• 어떤 값을 찾을 (탐색할) 때 정렬의 특징을 이용해 빨리 찾는 알고리즘
• 정렬되어있을 경우, 어떤 값을 찾을 떄: O(N) → O(lgN)
• 처음부터 생각하기 어려움, 쉬운 방법부터 생각
• 예) 1~4 숫자 중 특정 숫자를 찾을 때
  • 모두 탐색: O(N), 1부터 4까지 순서대로 비교 (1과 비교, 아니면 2와 비교, 아니면 3과 비교 ...)
  • 이진 탐색: O(lgN), 전체 숫자를 반으로 잘라 자른 것 중 가장 가까이 있는 숫자와 비교 (자른 후 1, 2 | 3, 4로 나뉨, 2와 비교, 더 크면 더 큰 무리(3, 4)를 3 | 4로 나눈 후 3과 비교)

2. 핵심 코드

• 아래 코드는 미리 외워둬야됨!

def search(start, end, target):  # start = 시작하는 인덱스, end = 끝나는 인덱스, target = 찾으려는 값
    if start == end:
        // ~~
        return
    
    mid = (start + end) // 2
    if nums[mid] < target:
        search(mid + 1, end, target)
    else:
        search(start, mid, target)

 

3. 연습 문제: 백준 1920 수 찾기

• 참조: https://www.acmicpc.net/problem/1920

1) 문제

• Q:
  • 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^31 보다 크거나 같고 2^31보다 작다.
• 출력:
  • M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
• 예제 입력 1:

5

4 1 5 2 3

5

1 3 7 9 5

• 예제 출력 1

1

1

0

0

1

2) 사전 계획 수립

• 아이디어
  • 처음 아이디어:
    • M개의 수마다 각각 어디에 있는지 찾기
    • for: M개의 수
    • for: N개의 수 안에 있는지 확인
  • 수정된 아이디어 (이진 탐색 적용):
    
    • M개를 확인해야 하는데, 연속하다는 특징 활용 가능? → 불가
    • 그러면 정렬해서 이진 탐색 가능?
      • N개의 수 먼저 정렬하기
      • M개의 수 하나씩 이진 탐색으로 확인 → 가능
• 시간 복잡도
  • 처음 시간 복잡도:
    • for: M개의 수 > O(M)
    • for: N개의 수 안에 있는지 확인 > O(N)
    • O(MN) = 1e10 → 시간 초과
  • 수정된 시간 복잡도:
    • N개의 수 정렬: O(N * lgN)
      • Note: x개의 수를 정렬할 때에는 항상 O(x * lgN)의 시간복잡도가 적용됨
    • M개의 수 이진 탐색: O(M * lgN)
    • O((N + M)lgN) = 2e5 * 20 = 4e6 → 가능
• 자료 구조
  • 탐색 대상 수 (N): int[]
    • 모든 수 범위: -2^31 ~ 2^31 > INT 가능
  • 탐색 하려는 수 (M): int[]
    • 모든 수 범위: -2^31 ~ 2^31 > INT 가능

3) 실습

# 입력이 있을 경우
# import sys
# input = sys.stdin.readline
# N = int(input())
# nums = list(map(int, input().split()))
# M = int(input())
# target_list = list(map(int, input().split()))

N = 5
nums = [4, 1, 5, 2, 3]
M = 5
targets = [1, 3, 7, 9, 5]

nums.sort() # 이진탐색 가능

def search(start, end, target):
    if start == end:
        if nums[start] == target:
            print(1)
        else:
            print(0)
        return
    mid = (start + end) // 2
    if nums[mid] < target:
        search(mid + 1, end, target)
    else:
        search(start, mid, target)

for each_target in target_list:
    search(0, N-1, each_target)

 

Tip

• 처음부터 생각하기 어렵기 때문에 쉬운 방법부터 생각하는 것 (e.g., for문 2번 사용, etc.) 추천
  • 어떤 값을 여러번 탐색해야 하는 경우 → 이진 탐색 사용 고려
  • 입력의 개수가 1e5 정도의 경우 → 이진 탐색 사용 고려

참조

1. 개발자 장고, https://youtu.be/D1ad7UCbWHY?si=VGtomjpx2oAJjEol
2.