Can someone please help me change this to a binary search! # include <iostream>
ID: 3679291 • Letter: C
Question
Can someone please help me change this to a binary search! #include <iostream> #include <ctime> #include <cstdlib> using namespace std; bool is_in(const int* sorted_array, int needle, int length_of_array){ //This is linear search... for (int j = 0; j < length_of_array; j++){ if (sorted_array[j] == needle){ return true; } } return false; //Change it to a binary search!!! } int main() { srand(time(0)); int n = 100; int gap = 5; int monotonic[n]; monotonic[0] = rand() % gap + 1; for (int j = 1; j < n; j++){ monotonic[j] = monotonic[j-1] + rand() % gap + 1; } if (is_in(monotonic, 9, n)){ cout << "Found it" << endl; } else { cout << "Not in there" << endl; } }
Explanation / Answer
Here is the modified code for you:
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
bool is_in(const int* sorted_array, int needle, int length_of_array){
//This is linear search...
/*for (int j = 0; j < length_of_array; j++){
if (sorted_array[j] == needle){
return true;
}*/
int low = 0, high = length_of_array - 1;
while(low <= high)
{
int mid = (low + high) / 2;
if(needle ==sorted_array[mid])
return true;
else if(needle < sorted_array[mid])
high = mid - 1;
else
low = mid + 1;
}
return false;
//Change it to a binary search!!!
}
int main() {
srand(time(0)); //Initializes seed.
int n = 100; //Defines the n to 100.
int gap = 5; //Defines gap to 5.
int monotonic[n]; //Creates an array monotonic of size 100.
monotonic[0] = rand() % gap + 1; //Fills the first position of array with value in the range, 1 - 5.
for (int j = 1; j < n; j++){ //For all the remaining elements in the array.
monotonic[j] = monotonic[j-1] + rand() % gap + 1; //Fill it with previous value + random value in range 1 - 5.
}
if (is_in(monotonic, 9, n)){ //Searches 9 in the array monotonic, by calling the function is_in().
cout << "Found it" << endl; //If true, prints "found it".
} else {
cout << "Not in there" << endl; //If not prints "Not in there".
}
}
If you need any refinements, just get back to me.