이진 탐색(Binary Search)
배열이 정렬되어 있을 때, 가운데 값과 비교하여 찾고자하는 값이 더 크면 오른쪽을 작다면 왼쪽을 탐색하는 방식 예시 [2, 5, 7, 9, 14, 19, 20, 24]가 있을 때 만약 2를 찾고 싶다면 가운데 값인 14와 비교를 하면 더 작기 때문에 다시 왼쪽 부분인 [2, 5, 7, 9]에서 같은 방식으로 반복한다. 최종적으로 2를 찾아 인덱스를 리턴하게 된다. 장점 시간복잡도가 log n으로 상당히 빠르다. 완전 탐색을 수행했을 때 시간 초과가 나는 여러 문제에서 활용될 수 있다. 구현 재귀로 구현 int recursive_binarySearch(vector arr, int start, int end, int target){ if(start > end) return -1; int mid = (star..
2022. 3. 3.
