c - 递归二分查找无法正常工作

Question

int BinarySearch(int A[], int p, int r, int value)
{
    int q = (p + r) / 2;

    if (A[q] == value)
    {
        return q;   //value found
    }
    if (p == q) 
    {
        return 0;   //not found
    }
    if (A[q] > value)
    {
        return BinarySearch(A, p, q, value);
    }
    else
    {
        return BinarySearch(A, q + 1, r, value); 
    }
} //binary search ends here

现在的问题是，每当我想搜索数组的最后一个元素时，这段代码就会出错。谁能解释一下为什么吗？

Answer 1

根据第一个索引 p 和最后一个索引 r 制定搜索结束情况，

int BinarySearch(int A[], int p, int r, int value)
{
    int q = (p + r) / 2;
    if( p > r )
    {
      return 0;
    }
    if (A[q] == value)
    {
        return q;   //value found
    }
    if (A[q] > value)
    {
        return BinarySearch(A, p, q-1, value);
    }
    else
    {
        return BinarySearch(A, q + 1, r, value); 
    }
}