이진 탐색

이진 탐색 Bnary Search

 

데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘

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

 

과정

1. 현재 데이터 셋의 중앙값(median) 선택

2. 중앙값 > 타겟 데이터(target data) 일 때 중앙값 기준으로 왼쪽 데이터셋 선택

3. 중앙값 < 타겟 데이터(target data) 일 때 중앙값 기준으로 오른쪽 데이터셋 선택

4. 1~3 반복하다 중앙값 = 타깃 데이터(target data) 일 때 종료

 

그림으로 표현하면 아래와 같다.