Algorithm/이론
이진 탐색 (Binary Search) - JAVA
이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 입니다. 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는 방법입니다. 시간 복잡도는 O(log n)입니다. 탐색 과정 현재 데이터에서 중앙값 선택 중앙값 > 탐색값 일 때 중앙 값을 기준으로 왼쪽데이터셋 선택 중앙값 < 탐색값 일 때 중앙 값을 기준으로 오른쪽데이터셋 선택 탐색값을 찾을 때까지 1 ~ 3번 과정 반복 구현 아래의 문제를 예시로 들어 이진탐색을 구현하였습니다. 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에..
