Array.BinarySearch() return value

Question

I have the following array:

double[] list = new double[] {0,0,100,100}

Why if I search for 29.6 I get -3?

Array.BinarySearch(list, 29.6)

I expected +1 or -1.

The Array.BinarySearch() documentation for the return parameter says:

The index of the specified value in the specified array, if value is found. If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value. If value is not found and value is greater than any of the elements in array, a negative number which is the bitwise complement of (the index of the last element plus 1).

But it does not says too much to me.

Perhaps you should familiarize yourself with the bitwise complement: http://stackoverflow.com/questions/791328/how-does-the-bitwise-complement-operator-work — Chris Dargis, Jul 11 '12 at 15:36

score 11 · Accepted Answer · answered Jul 11 '12 at 15:37

If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value.

The first element which is larger than 29.6 is 100, which has index of 2.

~2 is -3.

James Michael Hare · Answer 2 · 2012-07-11T15:42:52.657

You can use the '~' to take the bitwise complement which will give you the index of the first item larger than the search item.

If the Array does not contain the specified value, the method returns a negative integer. You can apply the bitwise complement operator (~) to the negative result (in Visual Basic, Xor the negative result with -1) to produce an index. If this index is greater than or equal to the size of the array, there are no elements larger than value in the array. Otherwise, it is the index of the first element that is larger than value.

From the MSDN

Thus if you had:

var pos = Array.BinarySearch(list, 29.6);

You can check:

if (pos < 0)
{
     Console.WriteLine("Not found, the result was {0} which is index {1}", pos, ~pos);
}

Which, in your case, means your -3 would indicate the index 2 is the first item larger than your search target.

score 1 · Answer 3 · answered Jul 11 '12 at 15:56

Here is your answer: "a negative number which is the bitwise complement of the index of the first element that is larger than value."

So in your case, your searched value (29.6) is less then 100 which is the 3rd element in your array list, the complement of 3 is -3, which is the answer you got.

Here I extended your example and created another array list (list2) with some different values then I searched same value like you 29.6, now this 29.6 value is smaller then 100 but greater then 25, and in my array list 100 is on position 4 and its complement is -4.

So I get the result -4, if I have searched 20 in my array list I would have get answer -3.

 double[] list = new double[] { 0, 0, 100, 100 };
        double[] list2 = new double[] { 10, 15, 25, 100 };

        int result = Array.BinarySearch(list, 29.6);
        int result2 = Array.BinarySearch(list2, 29.6);

        Response.Write("Your answer result:" + result.ToString() + "<br/>");
        Response.Write("Your answer result2:" + result2.ToString());

My Code result:

            Your answer result : -3
            Your answer result2: -4

I hope this helps.

Array.BinarySearch() return value

3 Answers3