arrays - 二进制搜索只使用长度？

Question

所以我写了一个二进制搜索函数，它接受一个整数数组、一个低索引搜索值、一个高索引搜索值和一个校验值:

int binarySearch(int d[], int low, int high, int check)  
{
int mid = (high-low)/2 + low;

if(low > high)
    return -1;

if(d[mid] == check)
    return mid;
else if(check > d[mid])
    return binarySearch(d, mid+1, high, check);
else
    return binarySearch(d, low, mid-1, check);
}

但是，我被要求编写一个只接受数据数组、数组长度和搜索值的二进制搜索函数？如果没有低变量和高变量，我怎么能做到这一点？我如何根据大小声明低变量和高变量？

int binSearch(int d[], int size, int check)

Answer 1

这将取决于语言。

在 C 中，可以通过更改指向数组头部的指针，而不是考虑整个数组，只考虑它的第二半。

if in 1st half:
    arr = arr // unchanged
    size = size/2 //only the size and thus end point change
if in 2nd half:
    arr = arr + size/2  //only the 2nd half is considered
    size = size/2 //and size is also changing

当从递归调用返回时，您当然需要将您在第 2 种情况下添加的间隙添加到答案中。

在 Java 中，你不能真正有效地做到这一点(假设你仍然想要递归二进制搜索)，因为数组是一个你不能(很好地)改变起点的对象。您当然可以创建相关子数组的副本 - 但这将失去二进制搜索的效率点。