最基本的算法:
int BinarySearch(
int arr[],
int len,
int searchKey)
{
int start = 0, end = len - 1, mid;
while (start <= end)
{
// 求中间的索引值
mid = (start + end) / 2;
if (arr[mid] == number)
{
// 查到了
return mid;
}
else if (arr[mid] < searchKey)
{
// 搜索范围缩小到后半部
start = mid + 1;
}
else if (arr[mid] > searchKey)
{
// 搜索范围缩小到前半部
end = mid - 1;
}
}
// 没查到
return -1;
}
用到递归的算法:
int BinarySearch(
const
int arr[],
int searchKey,
int start,
int end )
{
// 求中间的索引值
int mid = ( start + end ) / 2;
if ( searchKey == arr[ mid ] )
{
// 找到了
return mid;
}
else if ( searchKey < arr[ mid ] )
{
// 搜索范围缩小到前半部
return BinarySearch( arr, searchKey, start, mid - 1 );
}
else if ( searchKey > arr[ mid ] )
{
// 搜索范围缩小到后半部
return BinarySearch( arr, searchKey, mid + 1, end );
}
else
{
// 没有查找到
return -1;
}
}
使用迭代实现:
int BinarySearch(
const
int arr[],
const
int& len,
const
int& searchKey )
{
int start=0, end=len-1, mid;
while ( start < end )
{
mid = (start + end) / 2;
if ( searchKey > arr[mid] )
{
start = mid + 1;
}
else
{
end = mid;
}
}
if ( start > end )
{
return -1;
}
else
{
if ( searchKey == arr[start] )
{
return start;
}
else
{
return -1;
}
}
}
测试代码:
void testBinarySearch()
{
const int LEN = 8;
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
printf("查找到的索引号为:%d\n", BinarySearch(a, LEN, 5));
printf("查找到的索引号为:%d\n", BinarySearch(a, 5, 0, LEN-1));
}
int BinarySearch(
int arr[],
int len,
int searchKey)
{ int start = 0, end = len - 1, mid; while (start <= end) { // 求中间的索引值 mid = (start + end) / 2; if (arr[mid] == number) { // 查到了 return mid; } else if (arr[mid] < searchKey) { // 搜索范围缩小到后半部 start = mid + 1; } else if (arr[mid] > searchKey) { // 搜索范围缩小到前半部 end = mid - 1; } } // 没查到 return -1;}
用到递归的算法:
int BinarySearch(
const
int arr[],
int searchKey,
int start,
int end )
{ // 求中间的索引值 int mid = ( start + end ) / 2; if ( searchKey == arr[ mid ] ) { // 找到了 return mid; } else if ( searchKey < arr[ mid ] ) { // 搜索范围缩小到前半部 return BinarySearch( arr, searchKey, start, mid - 1 ); } else if ( searchKey > arr[ mid ] ) { // 搜索范围缩小到后半部 return BinarySearch( arr, searchKey, mid + 1, end ); } else { // 没有查找到 return -1; }}
使用迭代实现:
int BinarySearch(
const
int arr[],
const
int& len,
const
int& searchKey )
{ int start=0, end=len-1, mid; while ( start < end ) { mid = (start + end) / 2; if ( searchKey > arr[mid] ) { start = mid + 1; } else { end = mid; } } if ( start > end ) { return -1; } else { if ( searchKey == arr[start] ) { return start; } else { return -1; } }}
测试代码:
void testBinarySearch()
{ const int LEN = 8; int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 }; printf("查找到的索引号为:%d\n", BinarySearch(a, LEN, 5)); printf("查找到的索引号为:%d\n", BinarySearch(a, 5, 0, LEN-1));}
