[C] Recall Binary Search: Input: a list of n sorted integer values and a target

Question

[C]

Recall Binary Search:

Input: a list of n sorted integer values and a target value

Output: True if target value exists in list and location of target value, false otherwise

Method:

Set left to 1 and right to n

Set found to false

Set targetindex to -1

While found is false and left is less than or equal to right

Set mid to midpoint between left and right

If target = item at mid then set found to true and set targetindex to mid

If target < item then set right to mid – 1

If target  > item then set to left to mid + 1

Return the targetindex

Write a C function called binary_search().

Explanation / Answer

#include<stdio.h>

int binary_search(int [],int,int);
int binary_search(int list[],int n,int key)
{
int first,last,middle;
first=1;
last=n;
  
while(first<=last)
{
middle=(first+last)/2;
if(key==list[middle])
return(middle);
else
if(key>list[middle])
first=middle+1;
else
last=middle-1;
}
  
return -1;
}

int main()
{
int n,i,list[100],key,result;
printf("Enter the number of elements in array: ");
scanf("%d",&n);
printf(" Enter Elements of Array in Ascending order ");
  
for(i=0;i<n;++i)
{
scanf("%d", &list[i]);
}

printf(" Enter the key value to search:");
scanf("%d", &key);
  
result=binary_search(list,n,key);
  
if(result!=-1)
printf(" Key value is found at position : %d",result+1);
else
printf(" Key value is not present in the list!");

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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