CODEWITHSUNDEEP
c++binary-search
Soham Mafidar
Soham Mafidar

Reputation: 63

Two-Sum Problem using Binary Search Approach

The problem is as follows :-

Given an array of integers numbers and an integer target, return indices of the two numbers such that they add up to target. Eg:-

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

I coded the problem using binary search approach and my main looks like this :-

    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";
    }

It gives correct answer.

The problem is that when I am using this approach and returning the answer vector(which has both index) from function in Leetcode, it is giving me this error :-

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:- Why almost nobody has posted a binary search approach to this problem ?

Upvotes: 0

Views: 800

Answers (1)

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1539

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

To apply Binary Search algorithm, you need to sort the inputs, which would directly change the index of the array, that is no way convenient to use for this problem.

You may get correct result in your sample input cause your input array is sorted; but all inputs may not come in sorted order. Take care of this.

Upvotes: 1

Related Questions