# Untitled

irfann
plain_text
7 months ago
3.8 kB
0
Indexable
Never
```#include <stdio.h>
#include <stdlib.h>
// Function prototypes
int linearSearch(int arr[], int n, int target);
int sentinelSearch(int arr[], int n, int target);
int binarySearch(int arr[], int n, int target);
int fibonacciSearch(int arr[], int n, int target);
int main() {
int n, i, target;
printf("Enter the number of students who attended the training program: ");
scanf("%d", &n);
int *rollNumbers = (int *)malloc(n * sizeof(int));
printf("Enter the roll numbers of students (in random order):\n");
for (i = 0; i < n; i++) {
scanf("%d", &rollNumbers[i]);
}
printf("Enter the roll number to search: ");
scanf("%d", &target);
// Perform linear search
int linearResult = linearSearch(rollNumbers, n, target);
if (linearResult != -1) {
printf("Linear Search: Student with roll number %d attended the training program.\n", target);
} else {
printf("Linear Search: Student with roll number %d did not attend the training program.\n",
target);
}
// Perform sentinel search
int sentinelResult = sentinelSearch(rollNumbers, n, target);
if (sentinelResult != -1) {
printf("Sentinel Search: Student with roll number %d attended the training program.\n",
target);
} else {
printf("Sentinel Search: Student with roll number %d did not attend the training program.\n",
target);
}
// Sort the array for binary and Fibonacci search
// (Note: Implement a sorting algorithm or use a library function for sorting)
// Perform binary search
int binaryResult = binarySearch(rollNumbers, n, target);
if (binaryResult != -1) {
printf("Binary Search: Student with roll number %d attended the training program.\n", target);
} else {
printf("Binary Search: Student with roll number %d did not attend the training program.\n",
target);
}
// Perform Fibonacci search
int fibonacciResult = fibonacciSearch(rollNumbers, n, target);
if (fibonacciResult != -1) {
printf("Fibonacci Search: Student with roll number %d attended the training program.\n",
target);
} else {
printf("Fibonacci Search: Student with roll number %d did not attend the training program.\n",
target);
}
free(rollNumbers);
return 0;
}
// Implement the linear search function
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// Implement the sentinel search function
int sentinelSearch(int arr[], int n, int target) {
int lastElement = arr[n - 1];
arr[n - 1] = target; // Add target as the last element (sentinel)
int i = 0;
while (arr[i] != target) {
i++;
}
arr[n - 1] = lastElement; // Restore the last element
if (i < n - 1 || arr[n - 1] == target) {
return i;
} else {
return -1;
}
}
// Implement the binary search function
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Implement the Fibonacci search function
int fibonacciSearch(int arr[], int n, int target) {
// Determine the Fibonacci numbers
int fibMinusTwo = 0;
int fibMinusOne = 1;
int fib = fibMinusTwo + fibMinusOne;
while (fib < n) {
fibMinusTwo = fibMinusOne;
fibMinusOne = fib;
fib = fibMinusTwo + fibMinusOne;
}
int offset = -1;
while (fib > 1) {
int i = offset + fibMinusTwo;
if (i < n - 1 && arr[i] < target) {
fib = fibMinusOne;
fibMinusOne = fibMinusTwo;
fibMinusTwo = fib - fibMinusOne;
offset = i;
} else if (i >= n || arr[i] > target) {
fib = fibMinusTwo;
fibMinusOne -= fibMinusTwo;
fibMinusTwo = fib - fibMinusOne;
} else {
return i;
}
}
return -1;
}```