В контексте .NET / C # что такое бинарный поиск и как / почему я могу его использовать?

Question

Сегодня я впервые прочитал о бинарном поиске в Википедии и просто немного скользил по поверхности.Кажется, он используется для быстрого поиска элементов в коллекции, где не хватает памяти.

В контексте .NET / C # мне когда-нибудь понадобится использовать один?Используете ли вы их когда-либо при создании реального программного обеспечения для производства?

Извините, если эти вопросы звучат как подстрекательство, но я задаю настоящий вопрос, будучи студентом!

Answer 1

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

Единственное место, где я использовал бинарный поиск в реальном программном обеспечении, - это поиск по диапазону. Стоимость доставки указана для диапазона веса, поэтому может быть одна ставка для 0-1 фунта, одна для 1-5 фунтов, а другая для 5-10 фунтов. Если я позвоню List<T>.BinarySearch и найду 4 фунта, это даст мне первый индекс выше, чем 4 фунта, который я могу использовать, чтобы найти диапазон 1-5 фунтов. Словарь просто скажет мне, что 4 фунта не было найдено.

Для общих отсортированных данных вам лучше использовать SortedList или SortedDictionary .

Answer 2

Бинарный поиск работает только с отсортированными данными, поэтому, если у вас есть некоторый набор данных в C #, который, как вы знаете, отсортирован, вы можете выполнить бинарный поиск по нему.Лучше всего было бы использовать уже предоставленные реализации (например, List<T>.BinarySearch()), но если в используемой вами коллекции нет метода двоичного поиска, вы всегда можете написать один.

Вот пример использования встроенных библиотек:

// An ordered list of ints
List<int> ints = new List<int>() { 1, 4, 8, 20, 30, 44 };

// Search for 5 in the list
int ix = ints.BinarySearch(8);

// Display the index the element 8 was found at
Console.WriteLine(ix);

И да, вы определенно захотите использовать бинарный поиск при поиске отсортированных данных.

Answer 3

Некоторое время назад (когда я был студентом курса компьютерной инженерии) мне пришлось работать с алгоритмами поиска.Результатом такой курсовой работы стала статья.

Я разместил в своем блоге информацию о алгоритмах быстрой сортировки и двоичного поиска на C ++ .Хотя он написан на C ++, он должен предоставить вам как / почему для использования бинарного поиска.Также показано, как реализовать алгоритм двоичного поиска.Прилагается пример приложения, чтобы вы могли проверить его самостоятельно.