1

I am almost done with my Binary Search and yet when I test it, it does this strange thing. I run ./find (some number) and it prints out the haystack[] values one by one as I enter numbers for those, but then when I press [control] d to stop the haystacks, it simply goes into a blank line. I don't know why. But I do know it must have to do with my Binary Search code, as everything before it, worked fine.

bool search(int value, int values[], int n)
{   

    // TODO: implement a searching algorithm - binary search
    // Check for negative numbers, if true, return error
    if (n < 0) 
    {
        return 1;
    }

    int least = 0;
    int max = n - 1; 
    int mid = (least + max) / 2;
    // Iterate through the whole list  
    while (least <= max)
    {
        // Search top half of list
        if (value < values[mid])
            max = mid - 1;
        // Search bottom half of list
        else if (value > values[mid])
            least = mid + 1;
        else 
            return true; // Value is found when search is done
    }
    return false; // Goes here if value was never found after search 
}

enter image description here

I then ran gdb, and the values make no sense at all:

enter image description here

0
2

The code could exhibit a type of behaviour called an infinite loop. This means it never reaches an expected state where the loop would end, and so continues to run forever. Tip: To halt a program which has entered an infinite loop, press Ctrl+C.

The cause of the error is that the mid variable is not being recalculated. Note two lines of code which move the start (least) and end (max) of the search range:

  1. max = mid - 1;
  2. least = mid + 1;

These lines adjust the search "window" to start after, or before, the current mid value. This causes the mid to fall outside the search window. So when the code then checks the value at the mid, it is not checking the actual mid-point of the search window, but instead checking the value just outside it. The code will not be checking a new value, and so the expected condition will never be reached.

To correct this, mid must be re-calculated whenever least or max is updated.

2
  • Thanks Luke, getting rid of those - 1 and + 1 did the trick. Again, I got that code from somewhere, so I probably did not really know why it was used. I could have sworn I saw something in the videos that mentioned using the midpoint like that, but not sure where. Aye, I really see I have to know more about my code before I use it. Frustrating, since I already have so many questions already. For instance, I didn't find the Binary Search video very useful, because they used an entire function to do a search, which I don't know how to write. Oh well, I guess I'm learning. Thanks. – Azurespot Aug 25 '14 at 2:51
  • 1
    You're doing well. Errors like these are not uncommon, whatever the circumstances. For complicated problems I find it sometimes helps to write out the program with pseudo code, and manually draw out the state of the program as I read through the instructions. It also seems that following the videos too literally can lead to problems. Perhaps this is done intentionally to force you to understand the concepts, rather than doing it by rote. If you paste a URL for the video, we can check to see if the there's an error in their code. – Luke Van In Aug 25 '14 at 7:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .