Binary Search Return Error

[chelseaR]

Hello! So here is my code:

int binSearch(const vector<double> & data, int elem, int & comps) // a function that conducts a binary
                                                                  // binary search on a vector
{
    int x=0;
    
        if(data.size() > 0)
        {
            
        int beg=0;
        int end=data.size()-1; // finds the end of the vector
        int mid=(end+beg)/2; // computes the midpoint
        
        
       for(int i =0; i<data.size(); i++) // checks the entire length of the vector
        {
            if(elem== data[mid] || elem== data[beg] || elem== data[end]) // if the element is found, breaks
            {
                x =1;
                break;
            }
            else if(elem< data[mid]) // checks to see if the element is smaller than midpoint
            {
                
                end=mid; // assigns a new mid accordingly
                comps++;
            }
            else if(elem > data[mid]) // checks to see if the element is larger than the midpoint
            {
                comps++; // assigns a new mid accordingly
                beg=mid;
                
            }
        }
    }
        else
        {
            x=-1;
        }
    
    if(x==1)
    {
        x=1;
    }
    
    else
    {
        x=-1;
    }
    
    
    return x;
}

So this code is set to match a testing program. The program provides different vectors of different sizes, including a size zero vector. However, this code returns that it cannot find the element easily and passes those tests, but then when it tries to find the element, it doesn't return that it has found it, and fails the tests that involve returning the found element.

[dem7w2]

Can you post the failed test?

[chelseaR]

Here is the console window:

Testing binSearch function
    Test: Testing binSearch on size 0 vector - passed
    Test: Testing binSearch on vector of size 1. Element not found - passed
    Test: Testing binSearch on vector of size 1. Element Found - ********** FAILED **********
    Test: Testing binSearch on vector of size 20. Element not found - passed
    Test: Testing binSearch on vector of size 20. Element Found - ********** FAILED **********
    Test: Testing binSearch on unsorted vector - ********** FAILED **********

and here is the segment of the testing program that checks it

void testBinSearch(Tester & t)
{
    vector<double> test1;
    int comps=0;
    cout << "Testing binSearch function" << endl;
    //testing size 0 array
    t.test(binSearch(test1,17,comps)==-1, "Testing binSearch on size 0 vector");
    
    //testing size 1 array
    test1.push_back(0);
    t.test(binSearch(test1,17,comps)==-1,"Testing binSearch on vector of size 1. Element not found");
    t.test(binSearch(test1,0,comps)==0, "Testing binSearch on vector of size 1. Element Found");
    
    //testing a sorted larger vector
    for(int i=1; i<20; ++i)
    {
        test1.push_back(i);
    }
    t.test(binSearch(test1,44,comps)==-1,"Testing binSearch on vector of size 20. Element not found");
    t.test(binSearch(test1,12,comps)==12, "Testing binSearch on vector of size 20. Element Found");
    test1=seedVectorDouble(25);
    t.test(binSearch(test1,12,comps)==-2, "Testing binSearch on unsorted vector");
    
}

[dem7w2]

Well... there's a lot of issues here.
1) The formatting is pretty messed up which makes the code hard to read.
2)

     if(x==1)
    {
        x=1;
    }

This doesn't do anything
3) Inside your for loop, mid does not get set to its new value each time.
4) Your logic in the function as a whole seems a bit fuzzy.

You may want to rewrite this. Try using some pseudocode from wikipedia:

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imax >= imin)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if(A[imid] == key)
        // key found at index imid
        return imid; 
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else         
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key is not found
  return KEY_NOT_FOUND;
}

Your C++ implementation will be similar to this except a few things such as not using the "midpoint" function, and returning 1 or -1 instead of returning imid and KEY_NOT_FOUND;