Question

2. (10 pts) 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().

Answer 1

Code:

#include <stdio.h>
#include <stdbool.h>
int binary_search(int arr[], int right, int target_value) //METHOD binary_search();
{
   int mid,left=1, target_index=-1; //set left =1, right =n, target_index =-1;
bool found = false; //set found =false;
while (found == false && left <= right) { //while found==false and left<=right;
       mid = left + (right - left) / 2; //calcultion of mid between left and right;
if (target_value == arr[mid]) //if target == item at mid the found = true and target_index=mid;
{
   found = true;
target_index= mid;
       }
if (target_value < arr[mid]) //if target<item then right=mid-1;
right = mid - 1;
if (target_value > arr[mid]) //if target>item then left=mid+1
left = mid + 1;
}
return target_index; //return target_index
}
int main()
{
int n, i,target_value,index;
printf("Enter Size of Sorted List of integers : \n");
scanf("%d",&n);
int arr[n];
printf("Enter %d integer in sorted way : \n", n);
for(i=0;i<n; i++){
   scanf("%d",&arr[i]);
   }
   printf("Enter a integer number to search in the list :\n");
   scanf("%d", &target_value);
index = binary_search(arr, n, target_value);
if (index == -1)
       printf("Element is not present in list");
else
   printf("Element is present at index %d", index);
return 0;
}

Note:

1. Input list should be in ascending(sorted list) order to satisfy the while loop condition(left<=right; as mentioned in the question)

2. Should not enter any negative number or zero, as minimum value in the list is 1(left=1 ;as mentioned in the question);

OutPut1:

Enter Size of Sorted List of integers :
5
Enter 5 integer in sorted way :
4
6
8
13
94
Enter a integer number to search in the list :
13
Element is present at index 3
--------------------------------
Process exited after 21.52 seconds with return value 0
Press any key to continue . . .

OutPut2:

Enter Size of Sorted List of integers :
6
Enter 6 integer in sorted way :
4
6
8
10
21
56
Enter a integer number to search in the list :
7
Element is not present in list
--------------------------------
Process exited after 25.19 seconds with return value 0
Press any key to continue . . .