Answer:
Following are the program in the C++ programming Language.
#include<iostream> // header file
using namespace std; // using namespace
int binary_Searching(int arr[], int n, int key1) // function definition of binary search
{
int l1 = 0, h1 = n - 1, mid; // variable declaration
int r = 0; // holding result
while (l1 <= h1)
{
r++; // increment of r
mid =(l1 + h1) / 2; // calculating the mid value
if(arr[mid] == key1) // checking the condition if the searching value is mid value
{
return r; // return r
}
else if (arr[mid]<key1) // checking the condition
{
l1 = mid + 1;
}
else
{
h1 = mid - 1;
}
}
return r; // reurn r
}
int linear_Searching(int arr[], int n, int key1) // function definition
{
int k,index = -1; // variable declaration
for(k= 0;k<n;k++) // iterating over the loop
{
if(arr[k] == key1) // checking the condition
{
if(index == -1)
{
index = k;
break; // break the program
}
}
}
return index+1; // return the index
}
int main() // main method
{
int arr[20] = {101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600 };// declaring an array
int result=binary_Searching(arr,20,521); // calling the function binary serach
cout<<"Total number of Binary search comparisons: "<<result<<endl;
int reult1=linear_Searching(arr,20,521); // calling the function linear serach
cout<<"Total number of Linear search comparisons: "<<reult1<<endl;
return 0;
}
<u>Output:</u>
Total number of Binary search comparisons: 3
Total number of Linear search comparisons: 18
Explanation:
Here, we define the integer type function " binary_Searching()" and pass three integer type arguments in its parameter i.e., "arr[]" which is array type, "n", and "key1" and inside the function.
- we set three integer type variable and assign values in it "l1" to 0, "h1" to n-1, and "r" to 0.
- we set the while loop and pass the condition when the variable l1 is less than equal to the variable h1 then increment in the variable r by 1 after that, the addition of l1 or h1 is store in the integer variable "mid" for calculating the mid value.
- inside the while loop, we set the if statement and pass condition the variable arr[mid] is equal to the key1 then, return 1 otherwise is the arr[mid ] is less than key1 then, increment at mid and store in l1 otherwise decrement at mid and store in the variable h1.
Here, we define the integer type function "linear_Searching()" and pass three integer type arguments in its parameter i.e., "arr[]" which is array type, "n", and "key1" and inside the function.
- inside it, we set the for loop and pass condition if k is less than n then, we set the if statement and check if arr[k] is equal to the key1 then, again we set if conditional statement and check if index is equal to the -1 then, we initialize the value of k in index then, we break the loop .
- Then, we return index by increment of 1.
Finally, we set the main method "main()" inside it, we set an integer type array variable and pass elements init then, we call bothe the variable and passing the values in its parameter and store them in other integer variable and print the following results.
