ArrayList BinarySearch

Question

Я занят подготовкой к экзамену MCTS 70-536, в соответствии с книгой экзаменов (Microsoft Press - .NET Framework - самообучающийся учебный комплект для разработчиков приложений, второе издание), пример кода:

ArrayList al = new ArrayList();
al.AddRange(new string[] { "Hello", "world", "this", "is", "a", "test" });
Console.WriteLine(al.BinarySearch("this"));

Выводит значение '2' на консоль, потому что элемент 'this' находится в индексе 2. Согласовано, что это вывод, который я получаю, когда запускаю этот код.

Однако, если я бегу

Console.WriteLine(al.BinarySearch("world"));

Я ожидал бы получить значение 1 в консоли, так как «мир» будет в индексе 1, однако я получу значение -7?

Может кто-нибудь объяснить, как это работает?

Спасибо

Answer 1

Массив, в котором вы выполняете бинарный поиск, не отсортирован. Это требование для BinarySearch для работы.

Будучи не отсортированным, он сбивает с толку алгоритм поиска и заставляет его думать, что «мир» должен находиться на 7-м месте, но его нет в массиве: результат равен -7.

Answer 2

Взят непосредственно из документации MSDN ArrayList.BinarySearch (http://msdn.microsoft.com/en-us/library/5tzt7yz3%28VS.85%29.aspx)

Параметр значения и каждый элемент ArrayList должен реализовать IComparable интерфейс, который используется для сравнения. Элементы ArrayList уже должен быть отсортирован в увеличение значения в зависимости от рода порядок, определенный IComparable реализация; в противном случае результат может быть неверным.

Answer 3

Вопрос уже ответил, но добавил это для справки.

BinarySearch найдет элементы, используя отсортированный алгоритм. В вашем примере сортировка по умолчанию в алфавитном порядке, поэтому «мир» должен быть последним, следовательно, номер 7.

Вы увидите перегрузчик BinarySearch, который принимает объект IComparer. Не указывать это дает по умолчанию сортировку по алфавиту.

Но если вы реализовали метод "reverseSort", как предлагается в книге, то вам нужно было бы передать функции BinarySearch объект "reverseSort".

Как это;

Console.WriteLine(al.BinarySearch(al, new reverseSort()));

Также, как мне показалось довольно интересным, если вы реализуете класс reverseSort и создаете console.writeline, для которого сравниваются значения, результаты оказались не такими, как я ожидал. Я потратил немного времени, пытаясь понять, что это за алгоритм.

Answer 4

Из документации :

Начинающийся с нуля индекс значения в отсортированном ArrayList, если значение найдено;в противном случае - отрицательное число, которое является побитовым дополнением индекса следующего элемента, который больше значения, или, если элемента больше, побитовым дополнением числа Count.1009 * отсортировано слово.