5. 이진 탐색
<aside>
📌 목록
5.1. 이진 탐색 알고리즘이란
5.2. 이진 탐색 동작 예시
5.3. 이진 탐색 동작 단계
5.4. 이진 탐색 동작 소스코드 (Java)
5.5. 파라메트릭 서치(Parametric Search): 이진 탐색을 사용해 해결하는 문제
</aside>
5.1. 이진 탐색 알고리즘이란
이진 탐색
- 정렬되어 있는 리스트에서 특정 데이터를 빠르게 탐색하기 위해 사용하는 알고리즘임
<aside>
📌 순차 탐색과 이진 탐색
- 순차 탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법임
- 가장 기본적인 형태의 데이터 탐색 알고리즘임
- 순차 탐색의 예:
for 문
- 순차 탐색의 시간 복잡도: O(N)
- 이진 탐색
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법임
- 배열의 중간점을 기준으로 탐색함
- 이진 탐색 수행을 위해 탐색 범위를 지정해야 함
- 이진 탐색은 시작점(인덱스), 끝점(인덱스), 중간점(인덱스)을 이용해 탐색 범위를 설정함
- 중간점이 2개인 경우
: 중간 인덱스 값을 계산한 후 해당 값의 소수점을 제거한 인덱스의 값을 중간점으로 채택
</aside>
5.2. 이진 탐색 동작 예시
- 이미 정렬된 10개의 데이터 중 값이 4인 원소를 찾기

5.3. 이진 탐색 동작 단계
- 탐색 범위 지정하기
- 시작점(인덱스), 끝점(인덱스), 중간점(인덱스) 지정하기
- 중간점 위치의 값과 찾고자 하는 값을 비교하기
- 시작점 또는 끝점의 위치를 이동하기
- 위의 과정을 반복함
- 중간점 위치의 값이 찾고자 하는 값과 동일하면 반복을 종료함