[IN C WITH COMMENTS]The binary search algorithm that follows may be used to sear

Question

[IN C WITH COMMENTS]The binary search algorithm that follows may be used to search an array when the elements are sorted. This algorithm is analogous to the following approach for finding a name in a telephone book. a) Open the book in the middle, and look at the middle name on the page. b) If the middle name isn’t the one you are looking for, decide wither it comes before or after the name you want. Take the appropriate half of the section of the book you were looking in and repeat these steps until you land on the name you want. Algorithm for Binary Search 1. Let bottom be the subscript of the initial array element. 2. Let top be the subscript of the last array element. 3. Let found be false. 4. Repeat as long as bottom isn’t greater than top and the target has not been found. (a) Let middle be the subscript of the element halfway between bottom and top. (b) If the element at middle is the target Set found to true and index to middle. (c) Else if the element at middle is larger than target Let top be middle - 1 (d) Else Let bottom be middle + 1. 1. In the main function declare the following array: int my numbers[] = { 2430,4719,2247,1397, 155,2401,3015,2324, 670,2134, 469, 952,3881,3633,3459,4366, 19, 935,1610, 724, 4373,2111,4542,1596,4244,4822,4964,1504, 462, 652, 1561,4557,4791, 387, 522 ,513,4872,4569, 241,2662, 3241,2475,3664,4028,2064,3993, 572, 649, 418,3283, 4347,3207,3349, 100,3651,4194,4725,1276,1244, 722, 2019,1232,3491, 606, 261,2054,3699,3901,1471,4477, 1569, 438,1439,3028,1839,1692,1209,4500,4996,1097, 3565,3068,2911,4416, 579,3994,1291,2914,3728,1023, 868,3652,3458,1461,4763,3904,1822,4594, 900,1763, 1645,1933,4541, 517,2676,4744,1292,4498,3848,3508, 2425, 87,2627,2532,2375,3623,3112,932,1368, 501}; 2. Sort my numbers array using the sort function you implemented in Question 2 3. Ask the user to enter the number he is looking for, call the binary search function to determine if the number is in the array and the number of searches the function took to locate or to determine that the number is not found. Repeat as long as the user entered a positive number. 3 Sample Run : What value are you seeking enter a negative number to exit? 76 The value 76 was not found in the list of numbers. It took 7 searches to determine that the number is not in the sorted array. What value are you seeking enter a negative number to exit? 100 The value 100 was found in the list of numbers. It took 75 searches to locate that number in the sorted array. What value are you seeking enter a negative number to exit? -1 Thank you

Explanation / Answer

#include <stdio.h>
void sort(int input[],int no)
{
int size,i,j,temp,flag=0; //variable declaration
  
   size=100;

   for(i=0;i<size && flag==0 ;i++)
   {
       flag=1;
       for(j=0;j<size-i-1;j++)
       {
           if(input[j]>input[j+1]) // swapping numbers
           {
               temp=input[j];
               input[j]=input[j+1];
               input[j+1]=temp;
               flag=0;
           }
       }
   }

   searchh(input,no); // calling the binary search function

}
void searchh(int array[],int search)
{

int c, first, last, middle, n; //variable decaration

n=100;

first = 0;
last = n - 1;
middle = (first+last)/2; //condition check

while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf(" The value %d was found in the list of numbers. %d. ", search, middle+1); //if match found
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
if (first > last)
printf("The value %d was found in the list of numbers. ", search); //if match not found


}

int main()
{
int num;
int my_number[] = { 2430,4719,2247,1397, 155,2401,3015,2324, 670,2134, 469, 952,3881,3633,3459,4366, 19, 935,1610, 724, 4373,2111,4542,1596,4244,4822,4964,1504, 462, 652, 1561,4557,4791, 387, 522 ,513,4872,4569, 241,2662, 3241,2475,3664,4028,2064,3993, 572, 649, 418,3283, 4347,3207,3349, 100,3651,4194,4725,1276,1244, 722, 2019,1232,3491, 606, 261,2054,3699,3901,1471,4477, 1569, 438,1439,3028,1839,1692,1209,4500,4996,1097, 3565,3068,2911,4416, 579,3994,1291,2914,3728,1023, 868,3652,3458,1461,4763,3904,1822,4594, 900,1763, 1645,1933,4541, 517,2676,4744,1292,4498,3848,3508, 2425, 87,2627,2532,2375,3623,3112,932,1368, 501};
do
{
printf("What value are you seeking enter a negative number to exit? ");
scanf("%d",&num); // accepting the number from user
sort(my_number,num); //calling the sort function
}while(num>0);
  
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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