이진 탐색
- 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
- 시간 복잡도는 O(logN)이다.
- 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.
핵심 이론
- 오름차순으로 정렬된 데이터에서 아래의 4가지 과정을 반복하며, 내림차순이라면 조건을 반대로 하여 과정을 반복한다.
- 현재 데이터셋의 중앙값을 선택한다.
- 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
- 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
- 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.
문제 풀이
https://yurison.tistory.com/343
[백준/자바] 1920 - 수 찾기
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea
yurison.tistory.com
https://yurison.tistory.com/565
[백준/자바] 2343 - 기타 레슨
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] arr = new int[N]; int start = 0; int end = 0; for (int i = 0; i < N; i++) { arr[i]
yurison.tistory.com
https://yurison.tistory.com/566
[백준/자바] 1300 - K번째 수
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int k = sc.nextInt(); long result = 0; long start = 1, end = k; while (start
yurison.tistory.com
'공부 기록 > 알고리즘' 카테고리의 다른 글
| Do it! 알고리즘 코딩테스트 with JAVA - (16) 그리디 알고리즘 (0) | 2023.08.08 |
|---|---|
| Do it! 알고리즘 코딩테스트 with JAVA - (14) BFS(너비 우선 탐색) (0) | 2023.08.07 |
| Do it! 알고리즘 코딩테스트 with JAVA - (13) DFS(깊이 우선 탐색) (0) | 2023.08.04 |
| Do it! 알고리즘 코딩테스트 with JAVA - (12) 기수 정렬 (0) | 2023.08.03 |
| Do it! 알고리즘 코딩테스트 with JAVA - (11) 병합 정렬 (0) | 2023.08.03 |
