c++ - 双二分查找算法

Question

我目前正在为我的研究项目(第 49 页上的 The algorithm could be found here)解决双重二进制搜索问题。代码的每个 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 条件为真。这将一直持续到堆栈空间用完为止。

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