Wednesday, October 20, 2010

Given a sorted array find two elements with sum = c

in linear time
Pubblicato da a
Reazioni: 

1 comment:

  1. std::pair find_sorted(const std::vector& vin, int sum)
    {
    int start = 0;
    int end = vin.size()-1;
    while ( start < end ) {
    if ( vin[start]+vin[end] > sum ) {
    --end;
    } else {
    if ( vin[start]+vin[end] < sum ) {
    ++start;
    }
    else {
    return std::pair(start, end);
    }
    }
    }
    return std::pair(0, 0);
    }

    void test_find_sorted()
    {
    std::vector vin;
    vin.push_back(1);
    vin.push_back(3);
    vin.push_back(4);
    vin.push_back(5);
    vin.push_back(7);
    vin.push_back(9);

    std::pair res1= find_sorted(vin, 7);

    std::pair res2= find_sorted(vin, 11);
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)