C++ 二分查找的递归函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2648084/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive function for a binary search
提问by user317857
Create a recursive function for the binary search.
This function accepts a sorted array and an item to search for, and returns the index of the item (if item is in the array), or returns -1 (if item is not in the array).
Moreover, write a test program to test your function.
为二分查找创建递归函数。
该函数接受一个排序数组和一个要搜索的项目，并返回项目的索引（如果项目在数组中），或者返回 -1（如果项目不在数组中）。
此外，编写一个测试程序来测试您的功能。
template <class elemType>
int orderedArrayListType<elemType>::binarysearch
(const elemType& item) const
{
int first= 0;
int last = length -1;
int mid;
int list[];
int BinarySearch(,Type & Item, int first, int last)
bool found = false;
while (first <= last && !found){
mid = (first + last) / 2;
if (list[mid] > item)
return BinarySearch(list, item, first, mid -1)
found = true;
else if (list[mid] > item)
return BinarySearch( list, item, first, mid -1)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return -1;
}
回答by Eric J.
There's a child's game in the USA where one child picks a number between 1 and 10, and the other child has to guess that number. If they guess wrong, the first child says "higher" or "lower".
在美国有一种儿童游戏，一个孩子在 1 到 10 之间选择一个数字，另一个孩子必须猜出那个数字。如果他们猜错了，第一个孩子会说“更高”或“更低”。
Most kids start out guessing randomly, and will take about 4-5 tries on average to succeed. I realized (and this is probably why I ended up in computer science), that the best thing to do is pick the mid point (5.5, so pick either 5 or 6. I'll go with 5.). Based on what they say ("higher" or "lower"), select a new range, either 1-4 or 6-10. Pick the number in the middle of that range (2 or 8). Keep splitting the range in half until you get the number.
大多数孩子开始随机猜测，平均需要大约 4-5 次尝试才能成功。我意识到（这可能就是我最终选择计算机科学的原因），最好的办法是选择中点（5.5，所以选择 5 或 6。我会选择 5。）。根据他们所说的（“更高”或“更低”），选择一个新的范围，1-4 或 6-10。选择该范围中间的数字（2 或 8）。继续将范围分成两半，直到得到数字。
That's a binary search on a sorted array (the sorted array being numbers from 1 to 10).
这是对排序数组的二分搜索（排序数组是从 1 到 10 的数字）。
To implement that in code, just keep doing the same process described above. Pick the midpoint of the range, and create a new range based on the answer.
要在代码中实现它，只需继续执行上述相同的过程。选择范围的中点，并根据答案创建一个新范围。
Here's one solution in Javathat does this recurvively:
public class BinarySearchRecursive
{
public static final int NOT_FOUND = -1;
/**
* Performs the standard binary search
* using two comparisons per level.
* This is a driver that calls the recursive method.
* @return index where item is found or NOT_FOUND if not found.
*/
public static int binarySearch( Comparable [ ] a, Comparable x )
{
return binarySearch( a, x, 0, a.length -1 );
}
/**
* Hidden recursive routine.
*/
private static int binarySearch( Comparable [ ] a, Comparable x,
int low, int high )
{
if( low > high )
return NOT_FOUND;
int mid = ( low + high ) / 2;
if( a[ mid ].compareTo( x ) < 0 )
return binarySearch( a, x, mid + 1, high );
else if( a[ mid ].compareTo( x ) > 0 )
return binarySearch( a, x, low, mid - 1 );
else
return mid;
}
// Test program
public static void main( String [ ] args )
{
int SIZE = 8;
Comparable [ ] a = new Integer [ SIZE ];
for( int i = 0; i < SIZE; i++ )
a[ i ] = new Integer( i * 2 );
for( int i = 0; i < SIZE * 2; i++ )
System.out.println( "Found " + i + " at " +
binarySearch( a, new Integer( i ) ) );
}
}
回答by Seth Moore
You could also google"recursive binary search" and voila!
EDIT-Wikipedia knows all (especially when it comes to cs):
编辑 -维基百科无所不知（尤其是在 cs 方面）：
The most straightforward implementation [of the binary search algorithm] is recursive, which recursively searches the subrange dictated by the comparison:
[二分搜索算法]最直接的实现是递归，它递归地搜索比较指定的子范围：
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = low + ((high - low) / 2)
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
回答by IVlad
Just use std::binary_search. Tell the tutor that function is actually implemented recursively in your_favorite_compiler.
只需使用std::binary_search。告诉导师该函数实际上是在 your_favorite_compiler 中递归实现的。
