https://www.youtube.com/watch?v=1vZijMmhGNw&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=23
📌 이진탐색 (바이너리 서치)
- `데이터가 정렬 되어 있는 상태 에서 원하는 값을 찾아내는 알고리즘
- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 절반씩 줄이면서 대상을 찾음
- 구현 및 원리가 비교적 간단하며 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘
- N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있음
ex) 16개의 데이터인경우 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있음
| 특징 | 시간 복잡도 (노드 수 : V, 에지 수 : E) |
|---|---|
| 중앙값 비교를 통한 대상 축소 방식 | O(logN) |
◾ 이진 탐색 과정
- 현재 데이터셋의 중앙값을 선택
ex) 11개의 수가 있다면 6번째 값을 말함. - 중앙 값 > 타겟 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택
- 중앙 값 < 타겟 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택
- 중앙값 == 타겟 데이터일 때 탐색 종요
