You are to write a short C program along with a design tool that will load an ar

Question

You are to write a short C program along with a design tool that will load an array with values, then search for a value using a linear search, and then search the array (after sorting it) using a binary search.

Instructions:

Create an array. Load the array with 50000 random numbers.

Search the loaded array using a linear search for a value. Display the value, the location it was found, along with the number of looks for the value.

Sort the array. Search for the same value using a binary search. Display the value, the location it was found, and the number of looks for the value.

The simple Rule:

ALL CODE needs to be written using functions.  

Explanation / Answer

#include <stdio.h>
#include <math.h>

int main() {
  
   int index =-1;
   //Assuming the size of the array is 50000;
   int n = 50000;
   int arr[n];
   int i;
   //getting input to an array from the console
   for(i=0; i<n; i++){
       //can be modified as (arr[i] = rand() % 10000 + 1) to generate random numbers between [10000,1]
       //here we are taking as an input from the console.
       arr[i] = rand() % 10000 + 1;
   //   scanf("%d", arr[i]);
   }
   //Input the element to be searched
   int s;
   scanf("%d", &s);
   //Calling function to search for the element using linear search and storing the index value
   index = linearSearch(arr, s, n);
   //Calling function to search for the element using binary search and storing the location index value
   index = binarySearchUtil(arr, s, 0, n-1);
   if(index != -1){
       printf("The element %d is found at location index %d", s, index);
   }else{
       printf("The element %d is not present in the array", s);
   }
   return 0;
}

int linearSearch(int arr, int s, int n){
   int i;
   for(i=0; i<n; i++){
       if(arr[i] == s){
           return i;
       }
   }
   return -1;
}
// This function is a util function to call sort the array and then call the original binary search function
int binarySearchUtil(int arr[], int s,int start, int end){
  
   //sort an array using simple sorting algorithm
   int i,j,a;
   for (i = 0; i < n; ++i)
    {
        for (j = i + 1; j < n; ++j)
        {
            if (arr[i] > arr[j])
            {
                a = arr[i];
                arr[i] = arr[j];
                arr[j] = a;
            }
        }
    }
    int index = binarySearch(arr, s, 0, n-1);
    return index;
}

int binarySearch(int arr[], int s, int start, int end){
   //Using binary search on the above sorted array
    if (end >= start)
   {
        int mid = start + (end - start)/2;
        // If the element is present at the middle then retur mid
        if (arr[mid] == s) return mid;
        // If element is smaller than mid, then it can only be present in left subarray
        if (arr[mid] > s) return binarySearch(arr, s, 1, mid-1);

        // Else the element can only be present in right subarray
        return binarySearch(arr, s, mid+1, end);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.