Необходимо понять поведение методов BinarySearch и IndexOf

-2

У меня есть список и его значения («Бранденбург», «Алабама» и «Альберта»). Когда я использовал метод BinarySearch("Brandenburg"), он возвращает -4 вместо 0. но я могу получить правильный индекс при сортировке этого списка. Почему он возвращает неправильное значение, если я использую несортированный список ?. И у меня также есть правильный индекс от IndexOf("Brandenburg") метода. Какой метод полезен, что я могу использовать ?.Необходимо понять поведение методов BinarySearch и IndexOf

Спасибо заранее, Притхиви

источник

2016-09-19 Prithiv

Обычно binarysearch работает над отсортированным списком/массивом. Но вы также можете изменить, если ваш список соответствует определенному шаблону. Но в случае совершенно случайного порядка.binarySearch не будет работать – sinsuren

Итак, вы внимательно прочитали документацию для обоих методов ... прошу пояснить, что именно там не было ясно. –

, если вы посмотрите на определение бинарного поиска, вы увидите, что бинарный поиск - это алгоритм поиска, который находит позицию целевого значения в отсортированном массиве. поэтому он работает только на отсортированных массивах. для IndexOf, посмотрите здесь https://msdn.microsoft.com/en-us/library/k8b1470s(v=vs.110).aspx –

Он должен быть отсортирован, чтобы использовать бинарный поиск. Причина, по которой вы получаете -4;

Ваша коллекция не отсортирована и для бинарного поиска список будет «разрезан» пополам на каждой итерации. Итак:

Когда она начинается, то == TopIndex 0 и низ = 2

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

BinarySearch проверит деталь в середине: (2-0)/2 = 1. Если вы в поисках Brandenburg. Он будет сравнивать Alabama с вашим элементом поиска. Письмо B «больше», чем буква «A». Поэтому он перемещает topIndex в индекс 1.

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

Тогда он будет сравниваться со следующим «средним» предметом. В этом случае снова Alabama. (2-1)/2 = 1. Он также будет сравниваться с нижним индексом, но это последний.

Когда binarysearch возвращает отрицательное число, это означает, что элемент не может быть найден. Отрицательное число - это индекс, в который он должен быть вставлен.(-result -1) Итак, если вы хотите добавить новый товар, его следует добавить в индекс (--4 -1) == 3

источник

2016-09-19 06:28:09

Позвольте мне объяснить, как работает бинарный поиск.

Скажем у вас есть этот массив:

{1, 3, 5, 7, 10, 15, 20}

И я хочу, чтобы найти индекс 15. Что бинарный поиск будет делать то, что он смотрит на середине массива, 7. 7 больше или меньше чем 15? Если оно меньше 15, повторите то же самое снова во второй половине массива (10, 15, 20). Если оно больше 15, сделайте это в первой половине (1, 3, 5). Если оно равно 15, то это означает, что 15 найдено.

Это означает, что массив должен быть отсортирован для работы бинарного поиска. Это объясняет, почему выполнение двоичного поиска в вашем массиве возвращает отрицательное число. Потому что, очевидно, метод не может найти требуемую строку, используя алгоритм бинарного поиска.

Вы можете получить верный указатель с помощью IndexOf. Это потому, что IndexOf использует линейный поиск, чтобы найти элемент. Он смотрит на каждый элемент массива и сравнивается с тем, который вы находите. Поэтому вопрос о том, сортируется ли массив, не имеет значения.

Примечание: Я не читал исходный код IndexOf. Он может использовать двоичный поиск, если обнаружит, что массив отсортирован. Это только моя догадка.

источник

2016-09-19 06:47:19 Sweeper

Необходимо понять поведение методов BinarySearch и IndexOf

ответ

Смежные вопросы