(C PROGRAMMING) Recall Binary Search: Input: a list of n sorted integer values a
ID: 3771186 • Letter: #
Question
(C PROGRAMMING) 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 and test a C function called binary_search().
Explanation / Answer
#include <stdio.h>
void binar_search()
{
int c, left, right, middle, n, search, array[100];
printf("Enter number of elements ");
scanf("%d",&n);
printf("Enter %d integers ", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter value to find ");
scanf("%d", &search);
left = 0;
right = n - 1;
middle = (left+right)/2;
while (left <= right) {
if (array[middle] < search)
left = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d. ", search, middle+1);
break;
}
else
right = middle - 1;
middle = (left + right)/2;
}
if (left > right)
printf("Not found! %d is not present in the list. ", search);
}
int main()
{
binary_search();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.