-1

I have only included the function. I am trying to implement binary search but for some reason it is not working. What I am really trying to determine is whether the algorithm is correct. It appears fine to me....but may be I am wrong. I know that the algorithm has to be sorted first but that will be taken care of in another function. Is the algorithm wrong or right? For some unknown reason the programme hangs...I have taken care of all the headers etc....i am off target or what? Thanks. Function is in C.

bool search(int value, int values[], int n)
{
    int i;
    int begin = 0;
    int end = n-1;
    int middle = (begin + end)/2;

    for ( i = 0; middle <=end; i++)
        if (value == values[middle])
        {
            return true; 
            break;
        }
        else if (value > values[middle])
        {
            begin = values[middle +1];
        }
        else 
        {
            end = values[middle -1];
        }
    return false;
}
1

4 Answers 4

0

You do not need the loop on i.

Your loop would be on begin and end, such as while( begin < end )

Depending on how values[middle] compare with values[begin] and values[end], you have to adjust begin (begin = middle + 1;) or end (end = middle - 1;). Beware of the boundary cases!

1
  • I think this was the real big problem. Thanks to every one. The inputs have been rather invaluable.
    – kyzen
    Apr 1, 2014 at 3:08
0

(begin + end) / 2 may caused integer overflow in C. Try to use begin + (end - begin) / 2 instead.

1
  • Correct, but there are more pressing issues here
    – Arun
    Apr 1, 2014 at 2:54
0

What is the algorithm you have in mind ? I would suggest to go through the algorithm first . http://en.wikipedia.org/wiki/Binary_search

1
  • Providing little more than a link as an answer is not appropriate. You could either copy sufficient information from the link into the answer to answer the question, and just provide the link for additional reference, or post a comment instead, which you'll be able to do with a bit more reputation. Keep in mind that simply dumping the algorithm in an answer would not be particularly appropriate either - you'll need to actually explain what's wrong with the code in the question. Apr 1, 2014 at 18:09
-1

Your middle is calculating to the end. It should be middle = (end - begin) / 2

1
  • 1
    That would be true if begin and end were pointers. In this case, OP uses them as array indices, for example begin = 3 and end = 13, then middle should be (3 + 13)/2 = 8 (note 8 is equidistant from both 3 and 13), not (13 - 3)/2 = 5 (where 5 is not really the middle of 3 and 13).
    – Arun
    Apr 1, 2014 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.