Hi my task is to write a binary_search function using vector iterators and recur

Question

Hi my task is to write a binary_search function using vector iterators and recursion. It should find a value "val". Appreciate all help. this is what i got:

#include <cassert>
#include <vector>

typedef std::vector<int> Vec;
typedef Vec::const_iterator cIt;

cIt binary_search (cIt begin, cIt end, const int val) {
while(begin<=end){
if(begin==val)
return begin;
else
return binary_search(begin+1,end,val)
  
}
  
  
}

int main () {
  
Vec test1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Vec test2 = {-8, -8, -8, 15, 15, 28, 28};
Vec test3 (0);
  
assert(binary_search(test1.begin(), test1.end(), 2) == test1.begin()+1);
assert(binary_search(test1.begin(), test1.end(), 7) == test1.begin()+6);
assert(binary_search(test2.begin(), test2.end()-3, 28) == test2.end()-3 );
assert(binary_search(test2.begin(), test2.end(), 7) == test2.end() );
assert(binary_search(test3.begin(), test3.end(), 1) == test3.begin() );
assert(*binary_search(test2.begin(), test2.end(), -8) == -8 );
  
  
return 0;
}

Explanation / Answer

typedef std::vector<int>::const_iterator citer;

int binary_search( citer start, citer end, int value )
{
                 
    if( start == end )
    {
       return -1;
    }
    citer middle = start + (end-start)/2;
    if( value == *middle)
    {
       return middle - start;
    }
    else if ( value < *middle )
    {
       return binary_search( start, middle, value );
    }
    else // note the change here
    {
        int res = binary_search( middle+1, end, value );
        if( res == -1 )
           return -1;
        else
           return res + 1 + (middle-start);
    }

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.