Prithiv - 1 year ago 63

C# Question

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

`BinarySearch("Brandenburg")`

`IndexOf("Brandenburg")`

Thanks in Advance,

Prithivi

Answer Source

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`