c++ - 除法函数返回错误值

Question

我有一个函数可以检查是否有索引 i这样它就等于v[i] . V是一个严格升序的 vector 。需要在O(logn)中完成我想到了分水岭。我从来没有真正熟悉递归。我写了这段代码，但我真的不知道为什么它不起作用。有什么东西不见了。如果我把 cout << mid而不是 return 它将显示正确的值，但坦率地说，我想这不是正确的方法。这个阶段返回的mid值是7，不知道为什么。

这是代码。

int customDivide(vector <int>& v, int left, int right)
{
    if(left <= right)
    {
        int mid = (left+right)/2;
        if(mid == v[mid]){
            //cout<<mid<<" ";
            return mid;
        }
    customDivide(v,left,mid-1);
    customDivide(v,mid+1,right);
    }
}

Answer 1

这里存在两个问题，我将尝试用在您附近寻找丢失的狗的类比来解释它们。

1. 您不会从函数返回值，除非您立即找到正确的元素。您 promise 返回一个值(int)，但您并不总是这样做。

   这就像 promise 给狗主人写一封信，说明在哪里可以找到他们丢失的狗。你检查了你的花园，如果你找到了那只狗，你就寄一封信——行得通。如果你没有找到那只狗，你就去找你的邻居，让他们 promise 如果找到那只狗会给你一封信，使用与你所做的相同的方法(递归)。问题是，在这种情况下，您没有阅读或转发他们的信件(最后两个递归函数调用的返回值)-您只是将这些信件扔掉了。更糟糕的是，如果您自己没有找到狗，您实际上并没有将信寄回给正在寻找他的狗的人(电话后没有 return)。您的代码似乎假定邻居会自动将信件发送给狗主人 - 这不是 return 的工作方式，它只是将信件发送给链条中的前一个人(用代码术语来说， 调用堆栈)，所以如果那个人马上把它扔进垃圾桶，系统将无法工作。

2. 如果你无条件地递归到两边，你将无法获得 O(log(n)) 的性能。

   如果您总是询问您所有的邻居(并且他们询问了他们所有的邻居)，您几乎可以让附近的每个人都在寻找这只狗。那是 O(n)。您必须确定您的两个邻居中的哪一个应该寻找狗(例如，通过查看狗留下的踪迹)并且只问那个人。通过这种方式，您可以将每一步可能必须搜索狗的人数减半，从而获得 O(log(n)) 性能。

   这个“踪迹”是你需要事先知道的。在你的情况下，不清楚那可能是什么——狗可能在任何地方(所有元素都可能有随机值)，你不知道去哪里找。您需要弄清楚任务的这个细节才能达到 O(log(n)) 时间。可能是 vector 元素严格递增(参见@Jarod42 的评论)，即没有重复元素，每个元素都比前一个大。在这种情况下，您可以决定剩下的两半中只有一个可能包含您要查找的内容，从而在那里递归。

(是的，我知道，除非您的社区形状像一棵二叉树，您在顶部并且“邻居”的非互惠定义除外，否则类比不成立。)