Untitled

 avatar
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;
}
Leave a Comment