Я просматриваю список, и я вижу метод BinarySearch с несколькими перегрузками, и я не могу не задаться вопросом, имеет ли смысл вообще иметь такой метод в List?
Почему я хочу выполнить двоичный поиск, если список не был отсортирован? И если список не был отсортирован, вызов метода будет просто пустой тратой времени процессора. Какой смысл иметь этот метод в списке?
Сортировка и поиск - две очень распространенные операции над списками. Было бы неприемлемо ограничивать параметры разработчика, не предлагая бинарный поиск в обычном списке.
Проектирование библиотеки требует компромиссов - разработчики .NET решили предложить функцию двоичного поиска как по массивам, так и по спискам в С#, потому что они, вероятно, чувствовали (как и я), что это полезные и распространенные операции, и программисты, которые решили использовать их, понимают свои предпосылки (а именно, что список упорядочен) перед вызовом их.
Достаточно просто отсортировать List<T>, используя одну из перегрузок Sort(). Если вы чувствуете, что вам нужен инвариант, который сортирует данные, вы всегда можете использовать SortedList<TKey,TValue> или SortedSet<T>.
В дополнение к другим правильным ответам я замечаю, что бинарный поиск на удивление трудно писать правильно. Есть много угловых случаев и несколько сложных арифметических чисел. Поскольку бинарный поиск, очевидно, является общей операцией в отсортированных списках, команда BCL сделала мир службой, правильно написав алгоритм бинарного поиска, а не поощряя клиентов ко всем писать свой собственный алгоритм бинарного поиска; значительное число этих алгоритмов, разработанных клиентом, было бы неправильным.
BinarySearch имеет смысл только в List<T>, который сортируется, так же как IList<T>.Add имеет смысл только для IList<T> с IsReadOnly = false. Это беспорядочно, но это просто дело: иногда функциональность X зависит от критерия Y. Тот факт, что Y не всегда верен, не делает X бесполезным.
Теперь, на мой взгляд, это расстраивает то, что .NET не имеет общих методов Sort и BinarySearch для любой реализации IList<T> (например, как методы расширения). Если бы это было так, мы могли бы легко сортировать и искать элементы в любой коллекции без чтения, предоставляющей произвольный доступ.
Затем вы всегда можете написать свой собственный (или скопировать чужие).
Другие отметили, что BinarySearch весьма полезен для сортированного List<T>. Тем не менее, он не относится к List<T>, как тот, кто имеет опыт работы с C++ STL, сразу это узнает.
В связи с недавними разработками на языке С# имеет смысл определить понятие отсортированного списка (например, ISortedList<T> : IList<T>) и определить BinarySearch (и др.) В качестве методов расширения этого интерфейса. Это более чистый, более ортогональный тип дизайна.
Я начал делать это как часть библиотеки Nito.Linq. Я ожидаю, что первая стабильная версия будет через пару месяцев.
да, но List имеет метод Sort(), поэтому вы можете вызвать его перед BinarySearch.
Поиск и сортировка - это алгоритмические примитивы. Это полезно для стандартной библиотеки для быстрой надежной реализации. В противном случае разработчики теряют время изобретать колесо.
Однако, в случае .NET Framework, к сожалению, конкретный выбор алгоритмов делает их менее полезными, чем они могут быть. В некоторых случаях их поведение не определено:
List<T>.BinarySearch Если список содержит более одного элемента с тем же значением, метод возвращает только одно из вхождений и может возвращать любое из вхождений, не обязательно первое.
List<T> Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок не может быть сохранен. Напротив, устойчивая сортировка сохраняет порядок равных элементов.
Это позор, потому что есть детерминированные алгоритмы, которые так же быстры, и они были бы намного полезнее в качестве строительных блоков. Примечательно, что алгоритмы бинарного поиска в Python, Ruby и Go all находят первый соответствующий элемент.
Я согласен с тем, что полностью немой вызывать BinarySearch в несортированном списке, но он идеально подходит, если вы знаете, что ваш большой список отсортирован.
Я использовал его при проверке наличия элементов из потока в более или менее статическом списке из 100 000 элементов или более.
Двоичный поиск в списке имеет значение ORDERS больше, чем выполнение списка. Find, который на много порядков быстрее, чем поиск в базе данных.
У меня есть смысл, и я рад, что он там (не то, что это была бы ракетная наука, чтобы реализовать его, если бы это было не так).
Возможно, еще один момент состоит в том, что массив может быть одинаковым как несортированный. Поэтому теоретически наличие BinarySearch в массиве также может быть недопустимым.
Однако, как и во всех функциях языка более высокого уровня, они должны применяться кем-то с разумом и пониманием данных, иначе они потерпят неудачу. Конечно, некоторые кросс-чеки могут быть применены, и у нас может быть флаг, который сказал бы "IsSorted", и в противном случае он потерпит неудачу при двоичном поиске, но.....
Некоторые псевдо-коды:
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