0

Many sources say that you need to put "int l = n" the element next to last instead of "int l = n - 1"(int f = 0; int l = n - 1; int mid;) in my example. I am not sure why? Moreover it seems my code is working fine. Maybe I am wrong but where is the mistake then? Thanks for you help!

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

{

int f = 0; int l = n - 1; int mid;

if (value < values[0])

{

    return false;

}

else if (value > values[n - 1])  

{

    return false;

}

while (f < l)

{

    mid = (f + l)/2;

    if (value <= values[mid])

    l = mid;

    else 

    f = mid + 1;

}

if (values[l] == value)

{

    return true;

}

else

{

    return false;

}

}
0

I'm not sure I understand your question well, n is the number of array elements, really it does not matter if you manage well end values. If you say int l = n -1 probably you must change the WHILE condition to f <= l, the mid value is not too important, what matters is to have an array divided into two parts, and discard one on each iteration. I do not know if this answers your question.

1
  • The condition in the while is correct, and the code works correctly, but it's not as efficient as it can be. @MichaelLil if the value you search is exactly at the middle of the array, you find it from the first iteration, but don't return true. That makes your code to always run at log(n), instead of worst case O(log(n)). As @MARS correctly said, it doesn't matter if you assign n or n-1 if you take it into account in your code. – ChrisG Aug 20 '16 at 19:19

You must log in to answer this question.

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