[D-21] 탐색 - 이진

📍 이진탐색(binary search)

✅ 정의

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
시간복잡도는 O(logN)이다.
✔️ 정렬데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.
✔️ 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다.

이진탐색

✅ 핵심 이론

이진 탐색은 오름차순으로 정렬된 데이터에서 원하는 값을 찾아낸다.
(내림차순이라면 조건을 반대로 하여 과정을 반복한다.)

✅ 탐색 과정

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

출처 : [저작자] by penjee.com