Почему существует список <T>.BinarySearch (...)? - PullRequest
Новая
       22

Почему существует список <T>.BinarySearch (...)?

12 голосов
/ 15 июля 2010

Я смотрю на List и вижу метод BinarySearch с несколькими перегрузками, и я не могу не задаться вопросом, имеет ли вообще смысл иметь такой метод в List?

Зачем мне бинарный поиск, если список не отсортирован? И если список не будет отсортирован, вызов метода будет пустой тратой процессорного времени. Какой смысл иметь этот метод в списке?

Ответы [ 9 ]

22 голосов
/ 15 июля 2010

В дополнение к другим правильным ответам отмечу, что бинарный поиск на удивление трудно писать правильно. Есть много угловых случаев и хитрая целочисленная арифметика. Поскольку бинарный поиск, очевидно, является обычной операцией в отсортированных списках, команда BCL предоставила миру услугу, написав правильный алгоритм двоичного поиска один раз , вместо того, чтобы поощрять клиентов писать свой собственный алгоритм двоичного поиска; значительное число этих пользовательских алгоритмов будет неверным.

17 голосов
/ 15 июля 2010

Сортировка и поиск - две очень распространенные операции со списками. Было бы недружелюбно ограничивать возможности разработчика, не предлагая бинарный поиск в обычном списке.

Дизайн библиотеки требует компромиссов - разработчики .NET решили предложить функцию двоичного поиска по обоим массивам и спискам в C #, потому что они, вероятно, чувствовали (как и я), что это полезные и распространенные операции, и программисты, которые решили использовать их понять их предпосылки (а именно, что список упорядочен), прежде чем вызывать их.

Достаточно просто отсортировать List<T>, используя одну из перегрузок Sort(). Если вам кажется, что вам нужен инвариант, который сортирует гаранты, вы всегда можете использовать SortedList<TKey,TValue> или SortedSet<T>.

6 голосов
/ 15 июля 2010

BinarySearch имеет смысл только для List<T>, который отсортирован, точно так же, как IList<T>.Add имеет смысл только для IList<T> с IsReadOnly = false. Это грязно, но с этим просто нужно иметь дело: иногда функциональность X зависит от критерия Y. Тот факт, что Y не всегда верен, не делает X бесполезным.

Теперь, по моему мнению, досадно, что в .NET нет общих Sort и BinarySearch методов для любого IList<T> реализация (например, как методы расширения). Если бы это было так, мы могли бы легко отсортировать и поиск элементов в любой коллекции не только для чтения, обеспечивающей произвольный доступ.

Опять же, вы всегда можете написать свой собственный (или скопировать чужой ).

5 голосов
/ 15 июля 2010

Другие отметили, что BinarySearch весьма полезно для сортировки List<T>. Тем не менее, он не относится к List<T>, как любой, имеющий опыт работы с C ++ STL, сразу узнает.

В связи с недавними разработками на языке C # имеет смысл определить понятие отсортированного списка (например, ISortedList<T> : IList<T>) и определить BinarySearch (и др.) В качестве методов расширения этого интерфейса. Это более чистый, более ортогональный тип дизайна.

Я начал делать это как часть библиотеки Nito.Linq . Я ожидаю, что первый стабильный выпуск будет через пару месяцев.

2 голосов
/ 15 июля 2010

да, но у List есть метод Sort (), поэтому вы можете вызвать его до BinarySearch.

1 голос
/ 18 августа 2017

Возможно, еще один момент заключается в том, что массив может быть таким же несортированным. Таким образом, теоретически наличие BinarySearch в массиве также может быть недействительным.

Однако, как и для всех функций языка более высокого уровня, они должны применяться кем-то с разумом и пониманием данных, иначе они потерпят неудачу. Конечно, могут быть применены некоторые перекрестные проверки, и у нас может быть флаг, который говорит «IsSorted», и в противном случае он не будет работать при бинарном поиске, но .....

1 голос
/ 19 февраля 2014

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

Однако в случае .NET Framework, к сожалению, конкретный выбор алгоритмов делает их менее полезными, чем они могут быть.В некоторых случаях их поведение не определено:

  1. List<T>.BinarySearch Если список содержит более одного элемента с одинаковым значением, метод возвращает только одно из вхождений и можетвернуть любое из вхождений, не обязательно первое .

  2. List<T> Эта реализация выполняет нестабильную сортировку;то есть, если два элемента равны, их порядок может не сохраняться .В отличие от этого, стабильная сортировка сохраняет порядок элементов, которые равны.строительные блоки.Примечательно, что алгоритмы бинарного поиска в Python, Ruby и Go все находят первый соответствующий элемент.

1 голос
/ 15 июля 2010

Я согласен, что глупо вызывать BinarySearch в несортированном списке, но идеально, если вы знаете, что ваш большой список отсортирован.

Я использовал его при проверке, существуют ли элементы из потока в (более или менее) статическом списке из 100 000 или более элементов.

Двоичный поиск в списке на порядок быстрее, чем в списке. Поиск, который на много порядков быстрее, чем поиск по базе данных.

Я имею смысл, и я радэто там (не то, что это было бы ракетостроение, чтобы реализовать это, если бы не было).

0 голосов
/ 27 сентября 2017

Какой-то псевдокод: 

if List is sorted
   use the BinarySearch method
else if List is not sorted and you think sorting it is "waste of CPU time"
   use a different algorithm that is more suitable and efficient
...