Skip to content
Permalink
11b796b056
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Go to file
 
 
Cannot retrieve contributors at this time
52 lines (44 sloc) 2.78 KB
#include <iostream>
#include <string>
#include <vector> //extra include to use vectors
using namespace std;
bool binarySearch (int value, vector<int>sequence){ //the function for the binary search
cout << "Starting the search..." <<endl;
int left = 0; //initialize the left variable 0
int sequenceLen = sequence.size(); //length of the sequence
int right = sequenceLen - 1; //to determine right we have to subtract 1 from the length of the sequence
while (left <= right){ //a loop while the value left is less or equal to right
cout << "> "; //just for the looks
int mid = left * ((right-left) / 2); //formula to find the mid value
if (sequence[mid] == value) { //if the number is found (mid equals to value)
cout << "The number : " << value << " was found" << endl; //output message for success
return true; //meaning the value was found
} else if (value < sequence[mid]) { //number not found
cout << "Can't find " << value << " ... looking ..." << endl; //output message in case of a failed tasked
right = mid - 1; //formula for the new right value, to loop in a different way
} else { //number not found
cout << "Can't find " << value << " ... looking ..." << endl; //output message in case of a failed tasked
left = mid + 1; //formula for the new left value, to loop in a different way
}
}
return false;
}
int main()
{
vector<int> sequence; //the sequence of numbers that the function will be using for the search
int value;
cout << "Welcome to the binary search algorithm" << endl;
cout << "First I need you to provide us a sequence" << endl;
cout << "Type in as many numbers as you want, use ENTER to submit the number" << endl;
cout << "When finished, after the last number just type -1" << endl;
int n;
do { //a [do while] to help looping through the sequence input
std::cin >> n;
if (n == -1){ break;} //to stop the program from push_back [-1]
sequence.push_back(n); //adds the numbers to the vector
} while (n != -1); //do the function until the input is -1
cout << "Can you please provide us with a number from \n the sequence to start the binary search? " << endl;
cout << "Type in the number and press ENTER!" << endl;
cin >> value; //the number the function will be looking for
binarySearch(value, sequence); //call the function
}