?Write, compile, and run a C++ program that generates 200 random integers in bet

Question

?Write, compile, and run a C++ program that generates 200 random integers in between 1 to 200. Some of the randomly generated integers may be repeated as well. Next sort the randomly generated 200 integers using the Selection sort algorithm. Store the sorted numbers in an output data file. Then prompt the user to enter an integer in between 1 to 200 (inclusive) out of the keyboard as a key element. Next find out the location of the key element in the sorted array using both the binary search and the sequential search algorithms. The result returned by binary search and the sequential search algorithm may vary for repeated elements inside the sorted array. This is acceptable. Please write out the results returned by the binary search and the sequential search algorithms to the output data file.

Explanation / Answer

/**C++ program that generates a random array and prints
the sorted list. The prompt for key vlaue to find.
The program finds the index of the key value in the array
and prints the vlaue.

Note : Since the list is random list, there are repeating values
int the array.
In sequential search, the first index of the key is returnsed
whereas the binary search returns index of the mid position.
The results might be different for repeated array values.
But same for unique values.
*/

#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 sequentialSearch(int arr[], int size,int key);

int main()
{

   //array of size=200
   const int size=200;

   //declare an array
   int arr[size];

   //call fillarray
   fillarray(arr,size);  
   //call sort
   sort(arr,size);
   cout<<"Array : "<<endl;
   print(arr,size);

   int key;
   int pos;

   cout<<"Please enter a random key from keyboard in between 1 and 200 "<<endl;
   //read key vlaue
   cin>>key;
  
  
   pos=binarySearch(arr,key,0,size);
   if(pos!=-1)
   {
       cout<<"Key :"<<key<<" detected at index "<<pos<<" by Binary Search"<<endl;  
       //call binary search
       pos=sequentialSearch(arr,size,key);  
      
       cout<<"Next, Find out the key through Sequential Search : "<<endl;  

       if(pos!=-1)
           cout<<"Key :"<<key<<" detected at index "<<pos<<" by Linear Search"<<endl;  

   }
   else
   {
       cout<<"Key : "<<key<<" 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()%200;
}

//Print array values
void print(int arr[], int size)
{
   for(int index=0;index<size;index++)
       cout<<arr[index]<<endl;
}

//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
//and returns the index of element found otherwise returns -1
int binarySearch(int arr[], int key,int first,int last)
{

   if(first>last)
       return -1;
   else
   {

       int mid=(first+last)/2;

       if(arr[mid]==key)
           return mid;
       else if(arr[mid]>key)
       {
           binarySearch(arr,key,first,mid-1);
       }
       else
       {
           binarySearch(arr,key,mid+1,last);
       }
   }
}

//Method that takes array, key
//and returns the index of element found otherwise returns -1
int sequentialSearch(int arr[], int size,int key)
{

   int pos=-1;
   int found=0;
   for(int index=0;index<size && !found;index++)
   {      
       if(arr[index]==key)
       {
           pos=index;
           found=1;
       }
   }
   return pos;
}

-----------------------------------------------------------------------

Sample runs

sample run1:
Array :
0
1
2
3
4
4
5
6
7
7
8
8
13
13
13
13
13
14
15
15
15
15
16
16
17
17
19
19
19
21
22
22
25
26
26
28
30
32
33
33
36
39
41
41
42
43
43
45
45
46
46
48
49
50
50
50
51
54
54
58
58
58
59
61
61
61
62
62
64
64
65
65
66
66
66
66
67
69
70
71
72
72
73
73
75
77
81
82
82
84
89
92
93
94
96
97
98
99
99
100
101
105
107
108
110
111
111
112
112
114
114
115
115
116
116
117
118
120
121
126
127
127
128
128
129
130
130
131
132
132
133
133
133
134
136
136
138
141
142
142
142
148
149
150
150
151
151
152
152
154
156
156
156
157
159
159
161
161
161
163
163
163
163
164
166
166
167
168
169
169
169
170
171
172
174
175
175
176
176
176
177
177
179
180
183
185
186
186
188
189
190
190
191
192
192
194
194
195
196
199
Please enter a random key from keyboard in between 1 and 200
199
Key :199 detected at index 199 by Binary Search
Next, Find out the key through Sequential Search :
Key :199 detected at index 199 by Linear Search

sample run2:

Array :
0
1
1
1
3
3
4
4
5
6
10
12
15
16
17
18
18
18
18
18
18
19
20
21
23
25
25
26
28
30
30
33
33
33
34
34
36
36
36
36
37
39
39
41
41
41
42
42
43
44
45
46
47
48
48
49
49
50
51
51
53
55
56
56
57
57
58
59
59
59
60
60
62
63
63
63
66
68
69
69
70
70
71
71
71
72
73
73
73
74
75
75
76
76
77
78
81
85
86
88
90
91
93
94
94
95
96
96
97
98
100
101
101
101
102
104
104
106
106
106
107
108
109
110
110
111
113
114
115
116
116
117
117
117
117
117
121
121
124
125
127
127
131
132
133
137
137
139
139
140
141
141
142
142
142
143
144
146
147
148
149
149
152
152
154
155
160
162
162
163
165
165
167
170
171
172
172
175
176
177
178
178
178
179
181
183
184
185
185
186
188
191
194
194
194
196
197
197
198
199
Please enter a random key from keyboard in between 1 and 200
197
Key :197 detected at index 197 by Binary Search
Next, Find out the key through Sequential Search :
Key :197 detected at index 196 by Linear Search

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.