helping Linux users to harness the power of Linux ...

Example of binary search algorithm in C++

Last Updated on Friday, 07 May 2010 09:10

Here is a simple example of Binary Search in C++. The example first creates a vector of 4 000 000 numbers and then it makes a function call from main to Binary_Search function.

binary-search.cpp

#include <iostream>
#include <vector>

using namespace std;

void Binary_Search(const vector<int> &numbers, int value);

int main() {
   
vector <int>my_numbers;
  
for (int i=0; i<4000000; i++) my_numbers.push_back(i);

cout << "Size of vector my_nymbers :" << my_numbers.size() << endl; 
	Binary_Search(my_numbers, 2);
	Binary_Search(my_numbers, 23);
	Binary_Search(my_numbers, 234);
	Binary_Search(my_numbers, 7655);
	Binary_Search(my_numbers, 10101);
	Binary_Search(my_numbers, 895543);
	Binary_Search(my_numbers, 3785111);

return 0;
}

void Binary_Search(const vector< int> &my_numbers, int key) {

int iteration = 0, left = 0, right = my_numbers.size()-1, mid;

while (left <= right) {
	iteration++;
	mid = (int) ((left + right) / 2);
	if (key == my_numbers[mid]) {
		cout << "Binary search found " << my_numbers[mid] << " after " << iteration << " iterations.\n";
		iteration++;
		return;
	}
else if (key > my_numbers[mid])
	left = mid + 1;
else
	right = mid - 1;
}
cout << "Binary search did not found " << my_numbers[mid] << " after " << iteration << " iterations.\n";

return;

}

Compile:

$ g++ binary-search.cpp -o binary-search

Run:

$ ./binary-search

Output:

Size of vector my_nymbers :4000000
Binary search found 2 after 20 iterations.
Binary search found 23 after 21 iterations.
Binary search found 234 after 22 iterations.
Binary search found 7655 after 21 iterations.
Binary search found 10101 after 22 iterations.
Binary search found 895543 after 19 iterations.
Binary search found 3785111 after 22 iterations.

Share this linux post:

 

Comments for this page are closed !!!
Please visit our new Linux Forum for additional help or discussion.

---

Linux eBooks FREE Download