이진탐색
-
이분 탐색(binary search)알고리즘/탐색 2021. 12. 25. 01:05
이분 탐색 : 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교하여 원하는 결과를 도출해냄. 배열 내 데이터들이 정렬되어 있어야 사용할 수 있는 알고리즘이며, 입력 데이터가 많거나, 탐색 범위가 넓은 편. 시간복잡도: O(logN) 확인할 때마다 원소의 개수가 절반씩 줄어듦으로써 시간 복잡도는 logN에 비례하는 시간임. #include using namespace std; int binary_search(int arr[], int length, int target) { // 반복적 int start = 0; int end = length-1; int mid; while(start target) { end = mid-1; } else { ..