Почему там <T>.BinarySearch Списка (…)?
Я смотрю на Список, и я вижу метод BinarySearch с несколькими перегрузками, и я не могу сдержать удивление, если имеет смысл вообще иметь метод как этот в Списке?
Почему я хотел бы сделать двоичный поиск, если список не был отсортирован? И если бы список не был отсортирован, то называние метода просто было бы пустой тратой процессорного времени. Какой смысл того, чтобы иметь тот метод в Списке?
6 ответов
Сортировка и поиск - две очень распространенные операции в списках. Было бы недружелюбно ограничивать возможности разработчика, не предлагая бинарный поиск в обычном списке.
Дизайн библиотеки требует компромиссов - разработчики .NET решили предложить функцию двоичного поиска как в массивах, так и в списках на C #, потому что они, вероятно, чувствовали (как и я), что это полезные и распространенные операции, и программисты, которые решили их использовать понять их предпосылки (а именно, что список упорядочен), прежде чем позвонить им.
Достаточно легко отсортировать List , используя одну из перегрузок Sort () . Если вы чувствуете, что вам нужен инвариант, обеспечивающий сортировку, вы всегда можете использовать вместо него SortedList или SortedSet .
Я отмечаю в дополнение к другим правильным ответам, что двоичный поиск на удивление сложно правильно написать. Есть много угловых случаев и сложная арифметика с целыми числами. Поскольку двоичный поиск, очевидно, является распространенной операцией в отсортированных списках, команда BCL оказала миру услугу, правильно написав алгоритм двоичного поиска один раз , вместо того, чтобы побуждать клиентов писать свои собственные алгоритмы двоичного поиска; Значительное количество этих алгоритмов, созданных заказчиком, было бы неправильным.
BinarySearch имеет смысл только для отсортированного List , как и IList имеет смысл только для IList с IsReadOnly = false . Это беспорядочно, но с этим просто нужно иметь дело: иногда функциональность X зависит от критерия Y. Тот факт, что Y не всегда верно, не делает X бесполезным.
Теперь, по моему мнению, разочаровывает то, что в .NET нет методов general Sort и BinarySearch для любых Реализация IList (например, как методы расширения). Если бы это было так, мы могли бы легко сортировать и искать элементы в любой коллекции, не предназначенной только для чтения, обеспечивая произвольный доступ.
Опять же, вы всегда можете написать свое (или скопировать чужое ).
Другие отметили, что BinarySearch весьма полезен в отсортированном List. Однако на самом деле он не относится к List, как сразу поймет любой, у кого есть опыт работы с C++ STL.
С недавними разработками языка C# имеет смысл определить понятие отсортированного списка (например, ISortedList) и определить BinarySearch (и т. д.) как метод расширения этого интерфейса. Это более чистый, более ортогональный тип дизайна.
Я начал делать именно это как часть библиотеки Nito.Linq. Я ожидаю, что первый стабильный релиз будет через пару месяцев.
Я согласен, что вызывать BinarySearch для несортированного списка совершенно глупо, но это прекрасно, если вы знаете, что ваш большой список отсортирован.
Я использовал его при проверке, существуют ли элементы из потока в (более или менее) статическом списке из 100 000 или более элементов.
Двоичный поиск по списку выполняется НА ЗАКАЗ быстрее, чем по списку. Найти, что на много порядков быстрее, чем поиск по базе данных.
У меня есть смысл, и я рад, что это есть (не то чтобы это было ракетной наукой, если бы это не было).
да, но List также имеет метод Sort (), поэтому вы можете вызвать его перед BinarySearch.