#2.Update the followin program instructions are given,c++ data structures and al
ID: 3792575 • Letter: #
Question
#2.Update the followin program instructions are given,c++ data structures and algorithms. Thanks!
#include <iostream>
#include<stdlib.h>
using namespace std;
int sort(int array[], int n);
int main()
{
int array[1000], beg, mid, end, i, n=1000, num;
int sorted_array[1000];
int j;
for (int i = 0; i < n; i++)
{
array[i] = (rand() % n) + 1;
}
//Print the random number generated
/*for(int i = 0; i< n;i++)
{
cout<<array[i]<<' ';
}*/
//Sorting of array element
sort(array,n);
//Iniatialize beg and end value
beg = 0;
end = n-1;
cout << " Enter a value to be searched in an array ";
cin >> num;
// Run loop, while beg is less than end
for(i=0;i<1000;i++)
{
//Calculate mid value
mid = (beg + end)/2;
//If value is found at mid index then print the position and exit from the program
if(array[mid] == num )
{
cout << " Item found at position "<< (mid +1 )<<endl;
exit(0);
}
else if(num < array[mid])
{
end = mid-1;
}
}
cout <<"Value does not found"<<endl;
}
//Function Deination
//Implementation of bubble sort
int sort(int array[], int n)
{
int temp;
int i;
for (int x = 1; x <= n ; x++)
{
for (int i = 0; i < n-x; i++)
{
if (array[i] > array[i+1])
{
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}
}
Create an array that holds 1000 random integers between 1-1000. Allow the user to enter an integer to search Create and implement modified bubble sort algorithm which will sort the array before the Binary Search algorithm is executed. Create and implement a Binary Search Algorithm. If the number exists in the array and output the position. If the search key does not exist in the Array simple output value not found. Attach Photos of Source Code and OutputExplanation / Answer
#include <iostream>
#include<stdlib.h>
using namespace std;
int binarySearch(int inputArr[], int key,int n) {
int start = 0;
int end = n - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
}
if (key < inputArr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
//Implementation of bubble sort
int sort(int array[], int n)
{
int temp;
int i;
for (int x = 1; x <= n ; x++)
{
for (int i = 0; i < n-x; i++)
{
if (array[i] > array[i+1])
{
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}
}
int main()
{
int array[1000], beg, mid, end, i, n=1000, num;
int sorted_array[1000];
int j;
for (int i = 0; i < n; i++)
{
array[i] = (rand() % n) + 1;
}
sort(array, n);
//Print the random number generated
/*for(int i = 0; i< n;i++)
{
cout<<array[i]<<' ';
}*/
cout << " Enter a value to be searched in an array ";
cin >> num;
int index = binarySearch(array, num, n);
if(index != -1)
{
cout << " Item found at position "<< index<<endl;
exit(0);
}
else{
cout <<"Value does not found"<<endl;
}
}
Output:
sh-4.2$ g++ -o main *.cpp
sh-4.2$ main
Enter a value to be searched in an array 996
Value does not found
sh-4.2$ main
Enter a value to be searched in an array 445
Item found at position 459
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.