Write a program in C++ to find the number of comparisons using the binary search
ID: 3772466 • Letter: W
Question
Write a program in C++ to find the number of comparisons using the binary search and sequential search algorithms 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. Alternatively, you can use the function insertOrd to initially insert all the elements in the list.
c. Search the list for some items, as follows:
i. Use the binary search algorithm to search the list. (You might need to modify the algorithm given in this chapter to count the number of comparisons.)
ii. Use the binary search algorithm to search the list, switching to a sequential search when the size of the search list reduces to less than 15. (Use the sequential search algorithm for a sorted list.)
d. Print the number of comparisons for Steps c.i and c.ii. If the item is found in the list, then print its position.
Explanation / Answer
/**C++ program that generates a random array and prints
the sorted list. The prompt for key vlaue to find.
If array size is greater than 15, then calls the sequential search
and print element index and number of comaparisions
otherwise calls binary search
and print element index and number of comaparisions
*/
#include<iostream>
#include<time.h>
using namespace std;
//Function prototypes
void fillarray(int arr[], int size);
void print(int arr[], int size);
void sort(int arr[], int size);
int binarySearch(int arr[], int key,int first, int last, int &comparisions);
int sequentialSearch(int arr[], int size,int key, int &comparisions);
int main()
{
//array of size=1000
const int size=1000;
//declare an array
int arr[size];
//call fillarray
fillarray(arr,size);
//call sort
sort(arr,size);
cout<<"Sorted array : "<<endl;
print(arr,size);
int key;
int pos;
int seqComp=0;
int binComp=0;
cout<<"Enter element to search : ";
//read key vlaue
cin>>key;
//Check if size is less than 15 then call sequential search
if(size<15)
{
pos=sequentialSearch(arr,size,key,seqComp);
cout<<"Sequential Search"<<endl;
if(pos!=-1)
{
cout<<"Element is found at index "<<pos<<endl;
cout<<"Number of comparisions "<<seqComp<<endl;
}
else
cout<<"Element is not found"<<endl;
}
else
{
//call binary search
pos=binarySearch(arr,key,0,size-1,binComp);
cout<<"Binary Search"<<endl;
if(pos!=-1)
{
cout<<"Element is found at index "<<pos<<endl;
cout<<"Number of comparisions "<<binComp<<endl;
}
else
cout<<"Element is not found"<<endl;
}
system("pause");
return 0;
}
//Fill array with random values
void fillarray(int arr[], int size)
{
srand(time(0));
for(int index=0;index<size;index++)
arr[index]=rand()%1000;
}
//Print array values
void print(int arr[], int size)
{
for(int index=0;index<size;index++)
cout<<arr[index]<<" ";
}
//Sort the array in ascending order
void sort(int arr[], int size)
{
for(int i=0;i<size;i++)
{
for(int j=0;j<size-i-1;j++)
{
if(arr[j]>arr[j+1])
{
int temp;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
//Method that takes array, key, first,last and reference variable
//and returns the index of element found otherwise returns -1
int binarySearch(int arr[], int key,int first,int last, int &comparisions)
{
if(first>last)
return -1;
else
{
int mid=(first+last)/2;
if(arr[mid]==key)
return mid;
else if(arr[mid]>key)
{
comparisions=comparisions+1;
binarySearch(arr,key,first,mid-1,comparisions);
}
else
{
comparisions=comparisions+1;
binarySearch(arr,key,mid+1,last,comparisions);
}
}
}
//Method that takes array, key and reference variable
//and returns the index of element found otherwise returns -1
int sequentialSearch(int arr[], int size,int key, int &comparisions)
{
int pos=-1;
int found=0;
for(int index=0;index<size && !found;index++)
{
comparisions++;
if(arr[index]==key)
{
pos=index;
found=1;
}
}
return pos;
}
----------------------------------------------------------------------------
Sample output:
Sorted array :
6 12 17 28 33 40 47 52 56 57 59 60 60 72 76 77 78 83 94 106 135 146 146 157 157
160 167 172 175 181 211 229 241 242 263 265 266 269 271 289 306 314 325 330 355
366 366 370 373 378 379 404 405 418 422 427 437 438 450 464 477 478 484 494 507
509 517 528 533 537 539 544 551 571 575 577 597 603 605 615 624 640 641 645 650
661 669 672 673 674 690 693 694 698 698 699 700 710 713 722 756 757 760 760 768
776 780 782 782 810 814 817 824 825 845 848 849 860 872 875 875 879 888 889 902
904 925 926 932 937 938 939 948 950 952 952 963 979 988 1013 1017 1039 1043 1054
1057 1066 1072 1072 1097 1111 1119 1133 1145 1153 1155 1164 1165 1166 1168 1184
1190 1191 1194 1194 1194 1210 1219 1226 1231 1243 1264 1265 1268 1275 1278 1280
1282 1298 1320 1322 1340 1341 1346 1347 1348 1357 1381 1393 1404 1412 1417 1465
1467 1475 1486 1504 1506 1520 1526 1527 1529 1539 1543 1545 1547 1569 1592 1596
1598 1604 1609 1612 1619 1620 1626 1629 1635 1643 1643 1651 1652 1655 1661 1664
1676 1678 1682 1690 1694 1716 1727 1728 1731 1747 1771 1787 1788 1794 1797 1803
1820 1833 1841 1848 1865 1865 1868 1880 1881 1901 1904 1925 1958 1984 1984 1987
1990 2004 2010 2011 2017 2041 2051 2065 2083 2138 2141 2143 2145 2150 2159 2161
2163 2170 2176 2181 2187 2193 2195 2196 2196 2201 2219 2228 2233 2237 2237 2272
2272 2272 2273 2277 2279 2279 2280 2281 2284 2289 2290 2290 2290 2300 2303 2308
2310 2332 2343 2346 2357 2389 2393 2416 2420 2442 2447 2459 2459 2463 2477 2478
2479 2502 2519 2532 2534 2549 2549 2551 2556 2558 2564 2564 2581 2597 2601 2602
2611 2621 2631 2634 2644 2667 2667 2674 2685 2688 2705 2709 2715 2747 2750 2754
2759 2763 2767 2776 2794 2794 2800 2806 2831 2832 2836 2849 2894 2896 2900 2907
2908 2915 2933 2945 2955 2960 3012 3016 3023 3044 3047 3052 3076 3099 3101 3119
3138 3161 3167 3170 3174 3203 3221 3222 3238 3238 3255 3301 3303 3305 3311 3312
3314 3331 3342 3355 3371 3376 3388 3398 3400 3417 3447 3448 3459 3461 3463 3468
3473 3475 3486 3489 3510 3531 3534 3543 3546 3546 3546 3549 3564 3564 3568 3570
3604 3605 3609 3617 3621 3629 3643 3656 3666 3667 3677 3687 3726 3732 3738 3756
3756 3756 3785 3799 3802 3821 3827 3847 3854 3855 3858 3861 3864 3869 3871 3890
3892 3927 3940 3942 3949 3951 3959 3969 3985 3988 3991 3999 4016 4027 4031 4031
4043 4043 4050 4065 4067 4071 4078 4096 4097 4118 4139 4165 4174 4180 4197 4199
4205 4206 4216 4225 4236 4238 4251 4256 4261 4271 4304 4326 4333 4340 4340 4347
4354 4357 4371 4403 4416 4417 4427 4435 4437 4444 4454 4478 4484 4489 4501 4512
4535 4549 4550 4550 4573 4575 4582 4594 4599 4604 4606 4608 4642 4643 4669 4691
4705 4706 4708 4748 4769 4774 4782 4792 4804 4835 4846 4850 4858 4858 4859 4861
4880 4889 4893 4929 4948 4964 4978 4988 5016 5017 5034 5046 5071 5080 5080 5088
5091 5099 5107 5109 5117 5131 5150 5155 5157 5180 5185 5193 5215 5234 5259 5267
5289 5307 5315 5328 5335 5343 5357 5361 5404 5404 5422 5425 5436 5459 5461 5470
5477 5485 5486 5510 5531 5535 5548 5564 5572 5580 5597 5600 5605 5607 5616 5625
5632 5647 5654 5672 5673 5690 5692 5703 5729 5736 5749 5769 5781 5800 5804 5830
5835 5837 5842 5855 5860 5863 5881 5900 5948 5949 5954 5976 5977 5981 6006 6023
6024 6039 6041 6092 6094 6119 6120 6131 6133 6134 6136 6139 6151 6151 6172 6179
6184 6192 6194 6198 6200 6220 6240 6244 6253 6254 6280 6280 6286 6334 6344 6356
6377 6394 6396 6427 6444 6455 6483 6504 6532 6534 6537 6540 6544 6545 6570 6577
6609 6612 6614 6624 6626 6631 6633 6647 6650 6654 6654 6663 6666 6670 6674 6690
6717 6721 6726 6740 6750 6756 6765 6782 6785 6818 6833 6834 6842 6854 6855 6856
6878 6883 6905 6918 6920 6954 6969 6987 6991 7061 7150 7168 7168 7170 7212 7212
7241 7257 7260 7265 7266 7281 7319 7337 7360 7366 7389 7410 7424 7436 7436 7442
7448 7464 7475 7508 7523 7542 7566 7581 7586 7589 7593 7648 7650 7660 7669 7677
7687 7732 7784 7801 7817 7828 7836 7863 7874 7888 7901 7903 7919 7933 7935 7941
7945 7978 7981 8006 8007 8022 8031 8049 8061 8079 8080 8087 8121 8123 8141 8149
8152 8153 8160 8167 8180 8181 8194 8194 8214 8214 8218 8225 8227 8246 8250 8265
8266 8271 8283 8298 8331 8333 8353 8378 8403 8423 8431 8452 8458 8459 8496 8505
8507 8507 8513 8520 8528 8535 8541 8546 8584 8595 8598 8602 8610 8614 8640 8641
8642 8687 8688 8697 8704 8710 8715 8722 8724 8736 8738 8740 8749 8765 8767 8781
8790 8804 8808 8816 8816 8831 8839 8841 8851 8862 8863 8867 8874 8879 8880 8881
8891 8892 8900 8906 8928 8955 8960 8966 8985 8994 9003 9012 9013 9016 9039 9055
9063 9071 9076 9091 9112 9118 9118 9150 9150 9156 9158 9165 9187 9194 9203 9220
9232 9237 9240 9249 9254 9255 9265 9274 9276 9314 9332 9334 9338 9347 9354 9355
9357 9358 9383 9404 9409 9411 9412 9421 9447 9475 9509 9521 9548 9555 9581 9583
9590 9591 9597 9599 9601 9605 9608 9625 9627 9633 9641 9683 9696 9698 9707 9710
9712 9722 9726 9733 9738 9773 9780 9796 9842 9847 9862 9880 9886 9887 9900 9915
9919 9922 9925 9940 9967 9975 9989 9998 Enter element to search : 6647
Binary Search
Element is found at index 711
Number of comparisions 8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.