Binary Search (C++)

binarySearch.cpp

#include <iostream>
#include <vector>

bool binarySearch(std::vector<int>& v, const int& key, const int& start, const int& end);
void fillVector(std::vector<int>& v);
void printVector(std::vector<int>& v);

int main ()
{
  std::vector<int> testVector;
  
  fillVector(testVector);
  
  std::cout << "testVector : " << std::endl;
  printVector(testVector);
  
  int key = 22;
  std::cout << key;
  ( binarySearch(testVector, key, 0, testVector.size()-1) ) ? std::cout << " " : std::cout << " not ";
  std::cout << "found"  << std::endl;
  
  return 0;
}

/**
 * Binary search. 1st call with start=0 and end N-1
 * @param v The vector to be searched.
 * @param key The element we are searching for.
 * @param start The start of the set we currently looking into.
 * @param end The end of the set we currently looking into.
 * @return true for found, false for not found.
 */
bool binarySearch(std::vector<int>& v, const int& key, const int& start, const int& end)
{
    if(end < start)
        // Set is empty, return false
        return false;
    else
    {
        // Calculate midpoint to cut set in half
        int mid = (start + end)/2;
        
        if(v.at(mid) > key)
            // Key is in lower subset
            return binarySearch(v, key, start, mid-1);
        else if (v.at(mid) < key)
            // Key is in upper subset
            return binarySearch(v, key, mid+1, end);
        else
            // Key has been found
            return true;
    }
}

/**
 * Fills the vector with arbitrary data.
 * @param v The vector to be filled.
 */
void fillVector(std::vector<int>& v)
{
    for (int i=0 ; i < 25 ; i++)
      v.push_back(i);
}

/**
 * Prints the vector.
 * @param v The vector to be printed.
 */
void printVector(std::vector<int>& v)
{
    for (std::vector<int>::iterator it = v.begin() ; it != v.end() ; it++)
        std::cout << *it << ' ';
    std::cout << std::endl;
}

This code was developed by me, G. Samaras.

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

One thought on “Binary Search (C++)

  1. Just received this:
    Thanks to your binary search function on your homepage I was able to learn how to search a vector in C++. I wanted to show my appreciation with this mail. Thank you for your page.

    Regards / Patrik

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s