C++ only. Create a function that will allow the user to enter an integer value t
ID: 3602373 • Letter: C
Question
C++ only.
Create a function that will allow the user to enter an integer value to search. Program will implement a Binary Search algorithm to perform the search. Program will output if integer value is found and the location of the integer in the array or The program will output “value is not in array”. (It is ok for now for duplicate if duplicate values exist in the array. The goal is to correct implement the Binary Search and return a singular location of where the value exists in the array.) The array has to have 1000 random numbers from 1-1000. So, it needs to be sorted first (no library allowed), and then Binary Search. Plaese, be as simple and clear as possible. Thanks in advance.
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void bubbleSort(int array[], int n) {
int temp;
for(int i=0; i < n; i++){
int j=1;
while(j < (n-i)){
if(array[j-1] > array[j]){
//swap the elements!
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}
j++;
}
}
}
int binarySearch(int A[],int end, int v) {
int start = 0;
while (start <= end) {
int mid = (start + end) / 2;
if (v == A[mid]) {
return mid;
}
if (v < A[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
int main()
{
srand (time(NULL));
int a[1000];
int n;
for(int i=0;i<1000;i++) {
a[i] = rand() % 1000 + 1;
}
bubbleSort(a, 1000);
cout<<"Enter the value to be searched: "<<endl;
cin >> n;
int index = binarySearch(a, 1000, n);
if(index != -1) {
cout<<n<<" value is found at index "<<index<<endl;
} else {
cout<<n<<" value is not in array"<<endl;
}
return 0;
}
Output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.