이분탐색

문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net https://st-lab.tistory.com/285 해당 게시물을 참고하였습니다.  [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가..

이분 탐색데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 범위를 절반씩 줄이면서 대상을 찾는다.시간 복잡도: $O(logN)$ 이분 탐색 과정이분 탐색을 위해서는 데이터셋이 정렬되어 있어야 한다. 데이터 셋은 아래와 같다. 찾고자 하는 데이터(target)는 100이라고 가정하고 설명한다.  1. 현재 데이터 셋의 중앙값을 선택한다. left는 데이터 셋의 시작 인덱스, right는 데이터 셋의 마지막 인덱스이다. 중앙값의 인덱스는 (left + right) / 2 를 통해 알아낸다.중앙값인 30은 우리가 찾고자하는 100보다 작다. 따라서 30보다 작은 index 중 100은 절대 존재할 수 없으므로 데이터셋의 길이를 줄여준다. 100의 ..