Prithiv Prithiv - 2 months ago 11
C# Question

Need to understand the behaviour of BinarySearch and IndexOf methods

I have List and its values is ("Brandenburg","Alabama" and "Alberta"). When i used

BinarySearch("Brandenburg")
method, it returns -4 instead of 0. but i can get the correct index, when sorted this list. Why it returns wrong value if I use the unsorted list?. And I have also get the correct index from
IndexOf("Brandenburg")
method. Which method is useful that i can use?.

Thanks in Advance,
Prithivi

Answer

It MUST be sorted, to use binary search. The reason you're getting -4 is;

Your collection isn't sorted and for binary search the list will 'cut' in half each iteration. So:

When it starts, the topIndex == 0 and bottom = 2

TopIndex ->    (0) "Brandenburg",
               (1) "Alabama" 
BottomIndex -> (2) "Alberta

The binarysearch will check the item in the middle: (2-0) / 2 = 1. If you're searching for Brandenburg. It will compare Alabama with your search item. The letter B is 'bigger' than letter 'A'. So it moves the topIndex to index 1.

               (0) "Brandenburg",
TopIndex ->    (1) "Alabama" 
BottomIndex -> (2) "Alberta

Then it will compare to the next 'middle' item. In this case again Alabama. (2-1) / 2 = 1. It will also be compare to the bottomIndex, but this is the last one.

When binarysearch returns a negative number, it means that the item cannot be found. The negative number is the Index where it should be inserten. (-result -1) So if you want the new item added, it should be inserted on index (--4 -1) == 3