[알고리즘] 이진탐색

이진탐색 Binary search

데이터가 정렬되어 있는 상태에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다

O(logN) 시간 복잡도를 가진다

 

이진 탐색 동작

# 정렬 기준 오름차순

① 현재 데이터셋의 중앙값을 선택

② 중앙값 > 타깃 데이터 → 중앙값 기준으로 왼쪽 데이터셋 선택

③ 중앙값 < 타깃 데이터 → 중앙값 기준으로 오른쪽 데이터셋 선택

④ 1~3 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

→ 정렬 기준이 내림차순일 땐 2~3번 조건 반대로 실행

 

N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다

 

관련 문제보기

백준 1920번 수 찾기