- 이진탐색: 탐색 범위를 1/2씩 줄여나가는 알고리즘
- 과정
1. 데이터 집합의 중앙에 있는 요소를 고른다.
2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교.
3. 목표값 < 중앙값 이면 중앙값 왼편 탐색/ 목표값 > 중앙값이면 중앙값 오른편 탐색
4. 목표값이 나올때까지 1~3과정 반복
- 이진 탐색의 반복 횟수(데이터 개수 n개일 때) : log2n
-> 데이터 집합의 크기가 아무리 커져도 탐색 소요 시간은 아주 미미하게 증가한다는 것을 의미
**이진탐색 그냥 구현한 것도 작성해서 올리기**
- bsearch()함수로 이진탐색 구현
'알고리즘 &자료구조' 카테고리의 다른 글
| [알고리즘] 9. 우선순위 큐(Priority Queue) (0) | 2021.10.26 |
|---|---|
| [알고리즘] 7. 이진 탐색 트리 (0) | 2021.10.23 |
| [알고리즘] 5. 순차탐색 (0) | 2021.10.23 |
| [알고리즘] 4. c표준 라이브러리의 퀵 정렬 함수 (0) | 2021.10.21 |
| [알고리즘] 3. 퀵 정렬 (0) | 2021.10.21 |