Binary Search Vectors

Hi! So what I'm trying to do is write a program that fits to a separate test program. The test program provides different size vectors that my function should try and binary search. If the element is found, the function should return 1, and if the element is not found, it returns -1.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int binSearch(const vector<double> & data, int elem, int & comps)
{
    {
        int beg=data[0];
        int end=data[data.size()-1];
        int mid=(end+beg)/2;
        
        int begindex = 0;
        int endindex = data.size()-1;
        int midindex = (endindex-begindex)/2;
        
        while(begindex != endindex)
        {
            mid = (end+beg)/2;
            if(elem== mid)
            {
               
                int x= 1;
                comps++;
                return x;
            }
            else if(elem< mid)
            {
                
                endindex=midindex;
                end=data.at(endindex);
                comps++;
            }
            else if(elem > mid)
            {
                comps++;
                begindex=midindex;
                beg=data.at(begindex);
            }
        }
        return -1;
}
}


The problem is that one of the vectors my function is supposed to binary search is a vector of size 0. I tried to throw in an if statement that would return -1 if the size was == 0, but then the program never fully completed and just kept running.

So, how can I account for a size 0 vector in my function?
Last edited on
You can do one of the following:

1
2
while(begindex < endindex)
{...}


OR
1
2
3
#include <cassert>

assert(data.size() > 0);


OR
1
2
3
4
#include <exception>

if ( data.size() > 0)
    throw std::length_error("The size of the vector must be greater than 0!");
Last edited on
OR

1
2
3
if ( data.empty() ) {
  return -1;
}
Topic archived. No new replies allowed.