双二进制搜索算法

Question

我目前正在为我的研究项目（The algorithm could be found here，第49页）研究双二进制搜索问题。代码中的每个if / else部分都可以很好地工作，但是当我尝试将它们放在一起时，整个代码将导致无限循环。

代码的交互式链接是here，如果你想看一下我用printf来调试

#include <iostream>
#include <stdlib.h>
#include <set>
#include <vector>
#include <map>
#include <unordered_map>
#include <math.h>
using namespace std;

int binary_search(vector<int>& pos, int start, int end, int num, int& found)
{
    if (start > end) {
        //eventually will return position that the number is supposed to be in if not found
        return start;
    } else {
        int mid = start + (end - start)/2;

        if (pos[mid] == num) {
            found = 1;
            return mid;
        }
        if (pos[mid] < num) {
            return binary_search(pos, mid + 1, end, num, found);
        }
        else {
            return binary_search(pos, start, mid - 1, num, found);
        }
    }
}

vector<int> double_binary_search(vector<int>& vec_2, vector<int>& vec_1, int start_vec_2, int end_vec_2, int start_vec_1, int end_vec_1) 
{

    vector<int> intersection;
    if (end_vec_2 < start_vec_2 or end_vec_1 < start_vec_1) {
        return {};
    }

    int mid_vec_1 = start_vec_1 + (end_vec_1 - start_vec_1)/2;
    int mid_vec_1_val = vec_1[mid_vec_1];
    int found = 0;

    int mid_vec_2 = binary_search (vec_2, start_vec_2, end_vec_2, mid_vec_1_val, found);

    vector<int> res;
    //size of left 2 > size of left 1
    if ((mid_vec_2 - start_vec_2) > (mid_vec_1 - start_vec_1)) {
        res = double_binary_search(vec_2, vec_1, start_vec_2, mid_vec_2, start_vec_1, mid_vec_1);
        intersection.insert(intersection.end(), res.begin(), res.end());
    }

    else if ((mid_vec_2 - start_vec_2) <= (mid_vec_1 - start_vec_1)){// we exchange the roles of big vec and small vec
        res = double_binary_search(vec_1, vec_2, start_vec_1, mid_vec_1, start_vec_2, mid_vec_2);
        intersection.insert(intersection.end(), res.begin(), res.end());
    }   

    if (found == 1) {
        mid_vec_2++;
    }

    if ((end_vec_2 - mid_vec_2) > (end_vec_1 - mid_vec_1)) {
        res = double_binary_search(vec_2, vec_1, mid_vec_2, end_vec_2, mid_vec_1 + 1, end_vec_1);
        intersection.insert(intersection.end(), res.begin(), res.end());
    }

    else {// we exchange the roles of big vec and small vec
        vector<int> res = double_binary_search(vec_1, vec_2, mid_vec_1, end_vec_1, mid_vec_2 + 1, end_vec_2);
        intersection.insert(intersection.end(), res.begin(), res.end());
    }

    return intersection;

}

int main() 
{
    vector<int> vec_2 = {0,1,2,3,4,5,9,10,11,12,13,14,15,20,21,22,23,24,25};
    vector<int> vec_1 = {0,5,6,7,8,9,10,15,16,17,18};
    vector<int> sample = {11};
    vector<int> intersection = double_binary_search(vec_2, vec_1, 0, vec_2.size() - 1, 0, vec_1.size() - 1);  

    return 0;
}

Answer 1

如果start_vec_1 == end_vec_1和start_vec_2 == end_vec_2，你将递归调用double_binary_search相同的参数（虽然交换vec1和vec2），因为else if条件将为真。这将持续到你的堆栈空间不足为止。

您需要调整该条件，以便不会一直递归，和/或调整传递给递归调用的值（限制）。