Question

Given the following list of values, perform a binary search for the indicated search item. Use the binary search algorithm on pg. 1026 of our textbook. Show the values of first, last and middle, and the number of comparisons made after each iteration of the loop. Your should create a table like the following to show your work, where first and last are the values of the variables at the beginning of the loop, and mid is the midpoint used during that iteration, list[mid] is the value in the list at the midpoint, and No. of key comparisons should be the number of comparisons made during this iteration by the algorithm:

Iteration  first   last    mid  list[mid]   No. of key comparisons
1          0       12      ?    ?           ?

List:
[ 2, 3, 4, 4, 5, 7, 10, 14, 15, 17, 22, 23, 24 ]

Searching for value: 3

Answer 1

#include <stdio.h>

int main()
{
int f,l,mid,i,comp=0,key,n;
int list[20];
printf("enter no.of elements");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&list[i]);
printf("enter the element to search");
scanf("%d",&key);
f= 0;
l=n-1;
i=0;
mid=(f+l)/2;//caluculate mid
printf("Iteration\tfirst\tlast\tmid\tno.of comparisions\n");
while (f<= l) {//while the first value becomes greater than last then element not found
printf("%8d%12d%8d%8d%10d\n",i+1,list[f],list[l],list[mid],comp);//print values
i++;
if (list[mid] < key){//if mid is less than key it is in second half
f = mid+1;   
comp++;//increase comparisions
}
else if (list[mid] == key) {
comp++;//check if equals and increment comparisions
printf("%d found at location %d.\n", key, mid+1);
break;
}
else//if mid greater than key it is in first half
{
l= mid-1;
comp++;//increment comparisions
}
  
mid = (f+ l)/2;//change the mid value
}
if(f>l)
{
printf("The element not found");
}

return 0;
}