728x90
1. 이진 탐색
- 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다.
- 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
- 시간 복잡도는 O(logN)이다.
- 구현 및 원리가 비교적 간단하여 코딩 테스트에 많이 출제된다.
2. 이진 탐색 과정
- 현재 데이터셋의 중앙값을 선택한다.
- 중앙값 > 타깃 데이터일 때, 중앙값 기준 왼쪽 데이터셋을 선택한다.
- 중앙값 < 타깃 데이터일 때, 중앙값 기준 오른쪽 데이터셋을 선택한다.
- 과정 1~3을 반복하다가 중앙값 = 타깃 데이터일 때 탐색을 종료한다.
위 과정은 오름차순으로 정렬된 데이터일 때 이진 탐색 과정이다.
만약 내림차순 정렬 데이터이면 조건을 반대로 하여 과정을 반복하면 된다.
3. 예제 문제
[1920] 수 찾기 (JAVA)
# 문제 설명 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는
spicyrisotto.tistory.com
[2343] 기타 레슨 (JAVA)
# 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가
spicyrisotto.tistory.com
[10815] 숫자 카드 (JAVA)
# 문제 설명 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-12 소수 구하기 (0) | 2024.04.04 |
|---|---|
| Day-10,11 그리디 알고리즘 (0) | 2024.04.03 |
| Day-8 너비 우선 탐색 BFS (0) | 2024.03.29 |
| Day-8 깊이 우선 탐색 DFS (0) | 2024.03.29 |
| Day-7 계수 정렬 (0) | 2024.03.27 |
