Created
August 1, 2011 11:33
-
-
Save kazh98/1117979 to your computer and use it in GitHub Desktop.
Binary Search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Binary Search [License: CC-BY-SA] | |
* - Copyright(C) 2011 Kazh. All Rights Reserved. | |
*/ | |
#ifndef __INC_BINARYSEARCH | |
#define __INC_BINARYSEARCH | |
#include <stddef.h> | |
#include <iterator> | |
/** Search the item of the array by Binary Search Algorithm | |
* @tparam iter Random Access Iterator to access the array to search | |
* @tparam vtype Type of items in the array to search | |
* @param[in,out] begin Pointer to head of the array to search | |
* @param[in,out] end Pointer to tail of the array to search | |
* @param[in] item The item to search | |
* @return Pointer to the found item | |
* @retval NULL The item was not found in the array | |
*/ | |
template < | |
typename iter, | |
typename vtype | |
> | |
iter binarySearch ( | |
iter begin, | |
iter end, | |
vtype item | |
) | |
{ | |
size_t dist = std::distance ( begin, end ); | |
while ( dist > 1 ) | |
{ | |
iter middle = begin + dist / 2; | |
if ( *middle == item ) | |
{ | |
return ( middle ); | |
} | |
else if ( *middle < item ) | |
{ | |
begin = middle + 1; | |
} | |
else /* if ( *middle > item ) */ | |
{ | |
end = middle; | |
} | |
dist = std::distance ( begin, end ); | |
} | |
return ( NULL ); | |
} | |
/** Search the item of the array by Head Binary Search Algorithm | |
* @tparam iter Random Access Iterator to access the array to search | |
* @tparam vtype Type of items in the array to search | |
* @param[in,out] begin Pointer to head of the array to search | |
* @param[in,out] end Pointer to tail of the array to search | |
* @param[in] item The item to search | |
* @return Pointer to the found item | |
* @retval NULL The item was not found in the array | |
*/ | |
template < | |
typename iter, | |
typename vtype | |
> | |
iter binarySearchH ( | |
iter begin, | |
iter end, | |
vtype item | |
) | |
{ | |
size_t dist = std::distance ( begin, end ); | |
while ( dist > 1 ) | |
{ | |
iter middle = begin + dist / 2 - 1; | |
( *middle < item ? begin : end ) | |
= middle + 1; | |
dist = std::distance ( begin, end ); | |
} | |
return ( *begin == item ? begin : NULL ); | |
} | |
/** Search the item of the array by Tail Binary Search Algorithm | |
* @tparam iter Random Access Iterator to access the array to search | |
* @tparam vtype Type of items in the array to search | |
* @param[in,out] begin Pointer to head of the array to search | |
* @param[in,out] end Pointer to tail of the array to search | |
* @param[in] item The item to search | |
* @return Pointer to the found item | |
* @retval NULL The item was not found in the array | |
*/ | |
template < | |
typename iter, | |
typename vtype | |
> | |
iter binarySearchT ( | |
iter begin, | |
iter end, | |
vtype item | |
) | |
{ | |
size_t dist = std::distance ( begin, end ); | |
while ( dist > 1 ) | |
{ | |
iter middle = begin + dist / 2; | |
( *middle > item ? end : begin ) | |
= middle; | |
dist = std::distance ( begin, end ); | |
} | |
return ( *begin == item ? begin : NULL ); | |
} | |
#endif /* __INC_BINARYSEARCH */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
660f69
理論が割と不安。コードに何かあれば教えてください。