Write a program that has an array of at least 20 integers. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen. In order for us to have the same answers let's initialize an array with these 20 integer values: 101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600 Let's search for value 521. These are the parameters used for a successful run of the program.

Question

Computers and Technology

Maeve Novak

9 September, 14:51

Write a program that has an array of at least 20 integers. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen. In order for us to have the same answers let's initialize an array with these 20 integer values: 101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600 Let's search for value 521. These are the parameters used for a successful run of the program.

+3

Answers (1)

Know the Answer?

Kaylynn Chan · Answer 1

Following are the program in the C+ + programming Language.

#include / / 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]
{

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
{

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: "<
int reult1=linear_Searching (arr, 20,521); / / calling the function linear serach

cout<<"Total number of Linear search comparisons: "<
return 0;

}

Output:

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.