[알고리즘] 이진탐색

이진탐색

이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
탐색범위를 절반씩 좁혀가며 데이터를 탐색
코테에서 단골로 출제됨!

과정
시작점과 끝점을 확인한 후, 중간점을 정함(실수일 때는 소수점 이하 버림)
if) 시작점 : [0], 끝점 : [15] -> 중간점 : [7] 이때 찾으려는 데이터와 중간점의 데이터를 비교해서 찾으려는 데이터가 작으면, 끝점을 중간점 이전으로 설정해서, 중간점 이후를 버림
이 과정을 계속 반복

시간복잡도 O(logN) - 원소의 개수가 절반씩 줄어들기 때문

구현 방법

암기하자!

1. 재귀함수

def binary_search_recur(array, target, start, end):
  if start > end: # 시작점이 끝점보다 크면 찾으려는 데이터 없는 것
    return None
  mid = (start + end) // 2 
  # 중간점 찾기
  # mid = int((start + end) / 2) 와 같음
  # 찾으려는 데이터가 중간점의 데이터이면, 찾음 -> 중간점의 인덱스 반환  
  if array[mid] == target:
    return mid 
  elif array[mid] > target:
    return binary_search_recur(array, target, start, mid - 1)
  else:
    return binary_search_recur(array, target, mid + 1, end)
# 원소의 개수 n, 찾으려는 데이터 target
n, target = map(int, input().split())
# 전체 원소 입력 받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search_recur(array, target, 0, n - 1)
if result == None:
  print("원소 존재 X")
else:
  print(result + 1)

2. 반복문

def binary_search_iterable(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return None
n, target = map(int, input().split())
array = list(map(int, input().split()))
result = binary_search_iterable(array, target, 0, n - 1)
if result == None:
  print("원소 존재 X")
else:
  print(result + 1)

이진탐색은 입력 데이터가 많거나, 탐색범위가 매우 넓은 편이다. 그렇기 때문에 input() 함수를 사용하면 시간초과가 나올 수 있다
-> sys라이브러리의 readline() 함수를 이용하자

import sys
# 하나의 문자열 데이터 입력받음
input_data = sys.stdin.readline().rstrip() # rstrip() 꼭!
# 입력받은 문자열 그대로 출력
print(input_data)

관련 문제

• (백준) 공유기 설치
• (백준) K번째 수