please help me with this binary search

Question

for some reason this binary search code keeps returning true, when providing the haystack from generate.c, even if the "needle" isnt there. when manually inputing the haystack, the code runs perfectly. bool search(int value, int values[], int n) {

// TODO: implement a searching algorithm
// implement a binary search.

    int low = values[0];
    int high = values[n - 1];

    while(low <= high)
    {
        //make a mid    
        int mid = (low + high) / 2;
        //if value is less than mid
        if(value < mid)
        {
            high = (mid - 1);
        }
        //if value is more than mid
        if(value > mid)
        {
            low = (mid + 1);
        }
        //if value = mid, return true;
        if(value == mid)
        {
            return true;
        }
    }
    return false;

//end of search }

Answer 1

The code is setting low and high to the values contained in the values[] array, and calculating mid to be the average of those two values. All three of these values can be set to a value not contained in the array as the code loops. low and high should be set to the indexes of the array instead.

Think about it. Say that the values array contains 50, 55 and 70. On the first pass, values are set as follows: low = 50, high = 70, and mid = 60. On each subsequent pass, low or high will be recalculated to mid +/- 1. These values may or may not actually be array elements. So, as long as the target value is between the smallest and the largest values in the array, this code will report true, no matter what the remaining values are that are stored in the array.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)