使用二进制搜索方法的二和问题

Question

问题如下:-

给定一个整数数组和一个整数目标，return 两个数字的索引使得它们加起来等于目标。例如：-

Input: vec = [2,7,11,15], target = 9
Output: [0,1]
Output: Because vec[0] + vec[1] == 9, we return [0, 1].

我使用二进制搜索方法对问题进行了编码，我的主要内容如下所示：-

    vector<int>vec = {2,7,11,15};
    int flag = 0;
    int target = 0,i;
    int idx;
    vector<int>::iterator it;
    for(i=0;i<vec.size();i++)
    {

        if(binary_search(vec.begin()+i,vec.end(),target-vec[i]))
        {
            it = lower_bound(vec.begin()+i,vec.end(),target-vec[i]);
            idx = it-vec.begin();
            if (i!=idx)
            {
               flag = 1;
               break;
            }
        }
    }

    if(flag==1)
    {
        cout<<"Found @"<<idx<<"and "<<i<<endl;
    }
    else{
        cout<<"Not found";
    }

给出正确答案。

问题是，当我使用这种方法并从 Leetcode 中的函数 return 获取答案向量（具有两个索引）时，它给了我这个错误 :-

Line 1034: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:9

PS:- 为什么几乎没有人针对此问题发布二进制搜索方法？

Answer 1

Why almost nobody has posted a binary search approach to this problem ?

要应用二分查找算法，需要对输入进行排序，这会直接改变数组的索引，使用起来很不方便。

您的示例输入可能会得到正确的结果，因为您的输入数组已排序；但所有输入可能不会按排序顺序排列。照顾好这个。

使用二进制搜索方法的二和问题

Two-Sum Problem using Binary Search Approach

c++

binary-search