Question

In: Computer Science

IN C++ Write a program to find the number of comparisons using binarySearch and the sequential...

IN C++

Write a program to find the number of comparisons using binarySearch and the sequential search algorithm as follows:
Suppose list is an array of 1000 elements.

3 Search list for some items as follows:
a. Use the binary search algorithm to search the list. (You may need to modify the algorithm given in this chapter to count the number of comparisons.)
b. Use the binary search algorithm to search the list, switching to a sequentialsearch when the size of the search list reduces to less than 15. (Use the sequential search algorithm for a sorted list.)
Print the number of comparisons for Questions 3a and b. If the item is found in the list, then print its position.

Solutions

Expert Solution

a.

#include <iostream>

using namespace std;

//binary search algorithm
int binarySearch(int arr[], int min, int max, int target)
{
//in every recursive call we are comparing the element three time
//compare one
  
if (max >= min)
{
//Compute guess as the average of max and min
int guess = (max+min)/2;

//compare two
if (arr[guess] == target)
{

  cout<<endl<<"The item found at location: "<<guess<<endl;
return guess;
}
  
//compare three
if (arr[guess] > target)
return 3+binarySearch(arr, min, guess - 1, target);

return 3+ binarySearch(arr, guess + 1, max, target);
}
  
return 1;
}

//function to sort an array
void bubbleSort(int a[], int size)
{
//outer for loop
for(int i=0;i<size;i++)
{
//inner for loop
for (int j=0;j<size;j++)
{
if(a[i]<a[j])
{
//swap the values
int temp = a[i];
a[i]=a[j];
a[j] = temp;
}
}
}
}

int main()
{
//array declaration
int arr[1000];
  
//fill array with random number
for(int i=0; i<1000; i++)
{
//fill with random number
arr[i] = rand()%1000;
}
  
//method calling
bubbleSort(arr,1000);
  
//display the result
cout<<endl<<"The number of comparison in binary search = "<<binarySearch(arr,0, 1000, 800);
  
return 0;
}

OUTPUT:

The number of comparison in binary search = 31

b.

#include <iostream>

using namespace std;

//function to find an element using sequential search
int sequentialSearch(int arr[], int size, int target)
{
int countNumCom = 0;
for(int i=0; i<size; i++)
{
countNumCom++;
if(arr[i] == target)

{

  cout<<endl<<"The item found at location: "<<i<<endl;
return i;

}
}
  
return countNumCom;
}

//binary search algorithm
int binarySearch(int arr[], int min, int max, int target)
{
//in every recursive call we are comparing the element three time
//compare one
  
//if the size of the array is less than 15 then sequential search
if((max-min) <15)
{
int smallArr[max-min];
for(int i=0; i<(max-min); i++)
smallArr[i] = arr[min++];
  
int count = sequentialSearch(smallArr, (max-min), target);
  
return count;
}
if (max >= min)
{
//Compute guess as the average of max and min
int guess = (max+min)/2;

//compare two
if (arr[guess] == target)
{

  cout<<endl<<"The item found at location: "<<guess<<endl;
return guess;
}
  
//compare three
if (arr[guess] > target)
return 3+binarySearch(arr, min, guess - 1, target);

return 3+ binarySearch(arr, guess + 1, max, target);
}
  
return 1;
}

//function to sort an array
void bubbleSort(int a[], int size)
{
//outer for loop
for(int i=0;i<size;i++)
{
//inner for loop
for (int j=0;j<size;j++)
{
if(a[i]<a[j])
{
//swap the values
int temp = a[i];
a[i]=a[j];
a[j] = temp;
}
}
}
}

int main()
{
//array declaration
int arr[1000];
  
//fill array with random number
for(int i=0; i<1000; i++)
{
//fill with random number
arr[i] = rand()%1000;
}
  
//method calling
bubbleSort(arr,1000);
  
//display the result
cout<<"The number of comparison in sequential search = "<<sequentialSearch(arr, 1000, 800);
cout<<endl<<"The number of comparison in binary search = "<<binarySearch(arr,0, 1000, 800);
return 0;
}

OUTPUT:

The number of comparison in sequential search = 1000
The number of comparison in binary search = 25


Related Solutions

IN C++ Write a program to find the number of comparisons using binarySearch and the sequential...
IN C++ Write a program to find the number of comparisons using binarySearch and the sequential search algorithm as follows: Suppose list is an array of 1000 elements. 2 Use any sorting algorithm to sort list.
In C++ Write a program to find the number of comparisons using binarySearch and the sequential...
In C++ Write a program to find the number of comparisons using binarySearch and the sequential search algorithm as follows: Suppose list is an array of 1000 elements. 5.1 Use a random number generator to fill list.
Write a program in C++ to find the number of comparisons using binarySearch and the sequential...
Write a program in C++ to find the number of comparisons using binarySearch and the sequential search algorithm as follows: Suppose list is an array of 1000 elements. a. Use a random number generator to fill list. b. Use any sorting algorithm to sort list. c. Search list for some items as follows: i. Use the binary search algorithm to search the list. (You may need to modify the algorithm given in this chapter to count the number of comparisons.)...
Question 5 Write a program to find the number of comparisons using binarySearch and the sequential...
Question 5 Write a program to find the number of comparisons using binarySearch and the sequential search algorithm as follows: Suppose list is an array of 1000 elements. 5.1 Use a random number generator to fill list. 5.2 Use any sorting algorithm to sort list. 5.3 Search list for some items as follows: a. Use the binary search algorithm to search the list. (You may need to modify the algorithm given in this chapter to count the number of comparisons.)...
In JAVA!!! write a method called Comparisons that will return the number of comparisons to find...
In JAVA!!! write a method called Comparisons that will return the number of comparisons to find an element in the tree. The main program calls this method for each element, adding the comparisons each time in order to count the total number of comparisons. The program then outputs the total number of comparisons and the average number. You may use the program BuildTreeWIthMethod to build your tree. Then, after you have made the call to inOrder(root), add the following code:...
write a method called Comparisons that will return the number of comparisons to find an element...
write a method called Comparisons that will return the number of comparisons to find an element in the tree. The main program calls this method for each element, adding the comparisons each time in order to count the total number of comparisons. The program then outputs the total number of comparisons and the average number. You may use the program BuildTreeWIthMethod to build your tree. Then, after you have made the call to inOrder(root), add the following code: int totalComparisons=0;...
Write a C code program to implement the comparisons of three integer numbers, using only conditional...
Write a C code program to implement the comparisons of three integer numbers, using only conditional operators (no if statements). Please ask the user to input random three integers. Then display the minimum, middle, and maximum number in one line. Also, please calculate and display the sum and the average value (save two digits after decimal point) of these three integers. Please write the comments line by line.
c++ program that finds the number of comparisons of 1000 random numbers using  bubble, insertion, quick, shell,...
c++ program that finds the number of comparisons of 1000 random numbers using  bubble, insertion, quick, shell, selection, and merge sort.
Write a parallel program using Pthread based on given sequential solution. Please set the thread number...
Write a parallel program using Pthread based on given sequential solution. Please set the thread number as 10 in your code. Given Sequential Solution: #include <stdlib.h> #include <stdio.h> #include <string.h> #define MAX 10240 int total = 0; int n1,n2; char *s1,*s2; FILE *fp; int readf(FILE *fp) { if((fp=fopen("strings.txt", "r"))==NULL){ printf("ERROR: can't open string.txt!\n"); return 0; } s1=(char *)malloc(sizeof(char)*MAX); if(s1==NULL){ printf("ERROR: Out of memory!\n"); return -1; } s2=(char *)malloc(sizeof(char)*MAX); if(s2==NULL){ printf("ERROR: Out of memory\n"); return -1; } /*read s1 s2 from...
Write a C++ program to find the number of pairs of integers in a given array...
Write a C++ program to find the number of pairs of integers in a given array of integers whose sum is equal to a specified number.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT