이진탐색

[C++/JAVA] 이진탐색 (lower bound) (2021카카오 - 순위검색)

이진 탐색이란? 정렬된 데이터에서 특정 값을 찾아내는 divide n conquer 알고리즘. 탐색이 반복될 때마다 탐색 구간이 1/2씩 감소한다. (bigO logn) 원리 1. 데이터 집합의 가운데 원소(mid)와 타겟(target)을 비교 2. mid > target 인 경우 집합의 왼쪽 1/2 부분 탐색하여 1 반복 3. mid < target 인 경우 집합의 오른쪽 1/2 부분 탐색하여 1 반복 1. C++ (성공 코드 포함) 코드 int binarySearch(int *arr, int arr_sz, int target) { int left = 0; int right = arr_sz - 1; while(left target) { right = mid - 1; } else if (arr[mid] ..