Skip to content

Instantly share code, notes, and snippets.

@k06a

k06a/BinSearch

Last active December 21, 2015 06:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save k06a/6261834 to your computer and use it in GitHub Desktop.
Save k06a/6261834 to your computer and use it in GitHub Desktop.
Download ZIP
Binary search template function with searching nearest greater.
Raw
BinSearch
template<typename TI, typename TV>
int BinSearch(TI begin, TI end, TV value)
{
int minIndex = 0;
int maxIndex = end - begin - 1;
while (minIndex <= maxIndex)
{
int midIndex = (minIndex + maxIndex) / 2;
TI comparison = begin + midIndex;
if ((TV)*comparison == value)
return midIndex;
if ((TV)*comparison < value)
minIndex = midIndex + 1;
else
maxIndex = midIndex - 1;
}
return ~minIndex;
}
template<typename TI, typename TV>
int BinSearchNearestGr(TI begin, TI end, TV value)
{
int index = BinSearch(begin, end, value);
return (index < 0) ? ~index : index;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment