이진 탐색(Binary Search)

이진 탐색이란?

• 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음

  기능 : 타깃 데이터 탐색
  특징 : 중앙값 비교를 통한 대상 축소 방식
  시간 복잡도 : O(logN)

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

이진 탐색의 핵심 이론

• 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복

  1. 현재 데이터셋에서 중앙값을 선택

2. (중앙값 > 타깃 데이터)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택
3. (중앙값 < 타깃 데이터)일 때 중앙값 기준으로 오른쪽 데이터셋을 선택
4. 과정 1~3을 반복하다가 (중앙값 == 타깃 데이터)일 때 탐색을 종료