Why Array.BinarySearch() giving negative numbers?

Question

I have some code that isn't making much sense to me. I have an array of strings and I'm using a binary search to count them in a foreach() loop. The code is exactly the same both times I attempt output, other than sorting. I'm not sure why I'm getting the results I'm getting. I assume it should just count the array values the same way both time. Any help?

Code:

using System;
public class Driver {
    public static void Main(string [] args) {
        String [] s = {"Bob", "Jane", "Will", "Bill", "Liz"};

        Console.WriteLine("Before Sorting:\n----------");
        foreach(string item in s) {
            Console.WriteLine("{0}. {1}", Array.BinarySearch(s, item) + 1, item);
        }
        Console.WriteLine("Will is at position {0}", Array.BinarySearch(s, "Will") + 1);

        Console.WriteLine("\n\nAfter Sorting:\n----------");
        Array.Sort(s);
        foreach(string item in s) {
            Console.WriteLine("{0}. {1}", Array.BinarySearch(s, item) + 1, item);
        }
        Console.WriteLine("Will is at position {0}", Array.BinarySearch(s, "Will") + 1);
    }
}

Output:

Before Sorting:
----------
1. Bob
2. Jane
3. Will
0. Bill
-2. Liz
Will is at position 3

After Sorting:
----------
1. Bill
2. Bob
3. Jane
4. Liz
5. Will
Will is at position 5

I'm sure it's something entirely stupid, but I can't figure it out.

CrazyCasta · Accepted Answer · 2012-10-03 17:53:31Z

5

Binary search only works on sorted arrays. It is not finding the value:

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).

answered Oct 3, 2012 at 17:53

CrazyCasta

28.6k4 gold badges50 silver badges73 bronze badges

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

Comments

Reed Copsey · Accepted Answer · 2012-10-03 17:54:21Z

3

Array.BinarySearch requires that the array be sorted. From the documentation:

This method does not support searching arrays that contain negative indexes. array must be sorted before calling this method.

It will return negative values, by design:

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.

answered Oct 3, 2012 at 17:54

Reed Copsey

567k80 gold badges1.2k silver badges1.4k bronze badges

Comments

Alexei Levenkov · Accepted Answer · 2012-10-03 17:54:36Z

0

Binary search works on sorted array. You array is not sorted, so you are getting random results as expected.

answered Oct 3, 2012 at 17:54

Alexei Levenkov

101k15 gold badges138 silver badges189 bronze badges

Collectives™ on Stack Overflow

Why Array.BinarySearch() giving negative numbers?

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related