Linear, Binary, BinaryRecursive 서치
#include <stdio.h>
int arr[] = { 2, 3, 4, 9, 13, 14};
int LinearSearch(int ar[], int len, int target)
{
int i;
for (i = 0; i < len; ++i) {
if (target == ar[i]) {
printf("INFO: FOUND idx %d\n", i);
return i; //
}
}
printf("INFO: NOT FOUND\n");
return -1;
}
int BinarySearch(int ar[], int len, int target)
{
int first = 0;
int last = len - 1;
int mid;
while (first <= last) {
mid = (first + last) / 2;
if (target == ar[mid]) {
printf("INFO: FOUND idx %d\n", mid);
return mid;
}
else if (target < ar[mid]) {
last = mid - 1;
}
else {
first = mid + 1;
}
}
printf("INFO: NOT FOUND\n");
return -1;
}
int BinarySearchRecursive(int ar[], int first, int last, int target)
{
int mid;
if (first > last) {
return -1;
}
mid = (first + last) / 2;
if (target == ar[mid]) {
return mid;
} else if (target < ar[mid]) {
return BinarySearchRecursive(ar, first, mid - 1, target);
} else {
return BinarySearchRecursive(ar, mid + 1, last, target);
}
}
int main(void)
{
int idx;
idx = LinearSearch(arr, sizeof(arr) / sizeof(int), 14);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = LinearSearch(arr, sizeof(arr) / sizeof(int), 15);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BinarySearch(arr, sizeof(arr) / sizeof(int), 14);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BinarySearch(arr, sizeof(arr) / sizeof(int), 15);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BinarySearchRecursive(arr, 0, (sizeof(arr) / sizeof(int)) -1, 14);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BinarySearchRecursive(arr, 0, (sizeof(arr) / sizeof(int)) -1, 15);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}