Gemstone's Devlog

#include int BSearchRecur(int ar[], int first, int last, int target) { int mid; if (first > last) // 재귀함수의 탈출 조건 return -1; // -1의 반환은 탐색의 실패를 의미 mid = (first + last) / 2; // 탐색대상의 중앙을 찾는다. if (ar[mid] == target) return mid; // 탐색된 타겟의 인덱스 값 반환 else if (target < ar[mid]) return BSearchRecur(ar, first, mid - 1, target); else return BSearchRecur(ar, mid + 1, last, target); } int main(void) { int a..

순차 탐색 알고리즘 : O(n) 의 알고리즘을 이진 탐색 알고리즘 : O(logn) 의 알고리즘으로 개선시키는 것이 직접 연산횟수의 비교를 통해서 도대체 왜? 약간의 개선이 아닌 혁신적인 성능의 개선으로 간주되는지 알아보자. 비교를 위한 실험의 원칙은 다음과 같다. 1. 최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패를 유도한다. 2. 탐색의 실패가 결정되기까지 몇 번의 비교연산이 진행되는지를 센다. 3. 데이터의 수는 500, 5000, 50000일 때를 기준으로 각각 실험을 진행한다. #include int BSearch(int ar[], int len, int target) { int first = 0; int last = len - 1; int mid; int opCount = 0; /..