So I'm curious.. Why is it that I need to do 1 and -1 when truncating a side of the array. I get that an array is index based and starts at 0 but is that really the reason to why I need to do it? What's the actual logic behind it? I've noticed that if I don't do it, it just never exists the loop because it gets to a point where it just keeps dividing the values to the same value over and over again.

private static int[] values = { 1, 3, 5, 7, 10, 13, 15, 17 };
public static int FindValue(int valueToFind)
{
    int l = 0;
    int r = values.Length - 1;
    while (l <= r)
    {
        var mid = (l   r) / 2;
        if (values[mid] == valueToFind)
            return mid;
        if (values[mid] < valueToFind)
            l = mid   1;
        else
            r = mid - 1;
    }
    return -1;
}

CodePudding user response：

If instead of l = mid 1; we would have l = mid; then a problem arises when the l and r differ by at most 1 (so there are at most two array values in the running). In that case (l r) / 2 == l, so that mid will be equal to l. Now let's suppose the value we look for is greater than values[mid], then the if block will execute and l will be assigned mid. But it already had that value, so nothing changes! The next iteration will start with exactly the same state as the previous one, and we'll loop without end.

If you would replace r = mid - 1; with just r = mid, then a similar problem can arise when there is just one value in the array left, i.e. l and r are equal. If the value we look for is less than that only value values[mid], then r will be assigned mid, but again, it already had that value. Nothing changes, and the looping goes on for ever.

The reasoning to have the 1 and -1 in those assignments is that:

• it ensures that the interval will get smaller in each iteration, and so it will be impossible to have an infinite loop
• it excludes mid from the reduced range, which makes sense, as with the first if we already compared with the value at that index, so it is no longer a candidate.

CodePudding user response：

taking in your last comment, I would assume that it's a rounding issue. It's rounding up and the next calculated number is still higher than the target value. I would add some console logging to printout the value as it's searching.