C# Binary search returns negative indexes

Question

Today I've wrapped my head around binary search. I've heard this is the fastest method of finding indexes in big arrays. So I've decided to write code to see if I'll get an exception in case there was no index which I'm searching for.

int[] longArray = new int[1000];
Random rnd = new Random();

for (int i = 0; i < longArray.Length; i++)
{
    longArray[i] = rnd.Next(1, 1000);
}

Array.Sort(longArray);            

int indexOfMyNum = Array.BinarySearch(longArray, 706);
Console.WriteLine("Here it is: " +  indexOfMyNum);

Now the fun part, there was no exception, my program always returns number which is from time to time a negative one. I know that random wasn't necessary to see this behavior but I wanted to test it on the bigger array. Now my question is, why m'I getting negative index instead of an exception. Correct me if I'm wrong since indexes of an array are directly related to the memory addresses, does it mean that BinarySearch is looking on pieces of memory he shouldn't be allowed to, to see if my number is there?

Does anybody know why it happens instead of an exception?

Possible duplicate of Why Array.BinarySearch() giving negative numbers? — huse.ckr
– huse.ckr, Commented Dec 5, 2016 at 11:22

Community · Accepted Answer · 2020-06-20 09:12:55Z

5

Method documentation explains the "mystery":

Return Value

Type: System.Int32

The index of the specified value in the specified array, if value is found; otherwise, a negative number. If value is not found and value is less than one or more elements in array, the negative number returned 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 all elements in array, the negative number returned is the bitwise complement of (the index of the last element plus 1). If this method is called with a non-sorted array, the return value can be incorrect and a negative number could be returned, even if value is present in array. (emphasis added)

What this means is that your program is searching for a value not present in the array, and gets a bitwise complement of the insertion position, a negative number.

Does anybody know why it happens instead of an exception?

Quite bluntly, this happens because not finding an item in a collection is not an exceptional situation. After all, we often look for an item simply to see if it is there or not. BinarySearch method returninig a negative number fits this requirement, because callers can alwsys tell if the item is there or not, and if it's not there, what's the position for the insertion:

int indexOfMyNum = Array.BinarySearch(longArray, 706);
if (indexOfMyNum < 0) {
    int insertionPos = ~indexOfMyNum;
    Console.WriteLine("The number is not there; insert at {0}", insertionPos);
}

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Dec 5, 2016 at 11:19

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nethero Over a year ago

Does anybody know why it happens instead of an exception? At this stage of my programming education, I can't think of usage for this case. Maybe if I want to find the first bigger number in the array without writing if statement. Is this possible reason behind?

Dmitrii Bychenko · Accepted Answer · 2016-12-05 11:38:53Z

3

Negative return means that the value is in somewhere between the values in the array or beyond the array's range:

int indexOfMyNum = Array.BinarySearch(longArray, 706);

if (indexOfMyNum == -1)
  Console.WriteLine("The value is less than any item in the array");
else if (indexOfMyNum == -indexOfMyNum.Length - 1) 
  Console.WriteLine("The value is bigger than any item in the array");
else if (indexOfMyNum < 0)
  Console.WriteLine("The value is between [{0}..{1}]", ~indexOfMyNum - 1, ~indexOfMyNum);
else // exact match
  Console.WriteLine("Here it is: " +  indexOfMyNum);

edited Dec 5, 2016 at 11:38

answered Dec 5, 2016 at 11:29

Dmitrii Bychenko

188k20 gold badges178 silver badges231 bronze badges

1 Comment

Gardes Over a year ago

Спасибо за разъяснение, это именно то, что было мне нужно!

Collectives™ on Stack Overflow

C# Binary search returns negative indexes

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related