Skip to content

Instantly share code, notes, and snippets.

@Battleroid
Last active December 14, 2015 11:58
Show Gist options
  • Save Battleroid/5082924 to your computer and use it in GitHub Desktop.
Save Battleroid/5082924 to your computer and use it in GitHub Desktop.
Binary search for any data type using template for C++. Does not return true/false, but instead returns index of element searching for. Not entirely sure if it works, don't care enough to find out.
#ifndef BINARYSEARCH_H
#define BINARYSEARCH_H
template<typename T>
int binarySearch(T list[], T key, int size) {
int low = 0;
int high = size - 1;
while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid])
high = mid - 1;
else if (key == list[mid])
return mid;
else
low = mid + 1;
}
return -low - 1; // -low - 1?
}
#endif
#include "BinarySearch.h"
#include <iostream>
using namespace std;
int main () {
int list[] = {1, 5, 4, 3, 2, 7, 9};
// output should be index of '5', or '1'
cout << "Index of '5' is " << binarySearch(list, 5, 7) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment