Как сделать поиск в c

Обновлено: 02.07.2024

Последний комментарий : (26 сентября 2019 11:40) Взято с сайта Microsoft(((((Читайте лучше от туда инфу. читать. написать комментарий.

public T Find (Predicate match)

Описание
Метод возвращает найденный элемент по критерию (задаем функцию)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
<
class Program
<
class Book
<
public int Price < get; set; >
public string Name < get; set; >
>

Favorite

Добавить в избранное

Вступление

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

Линейный поиск

Этот алгоритм будет выполнять последовательный поиск элемента в заданном массиве. Каждый элемент проверяется от начала до конца, и если совпадение найдено, будет возвращен индекс соответствующего элемента; в противном случае -1 будет возвращено.

Псевдокод для линейного поиска

Позвольте нам понять это с помощью примера.

Рассмотрим массив ниже.

Если мы хотим определить позицию числа 1 в этом массиве, мы должны пройти каждый элемент от начала до конца; т.е. от index = 0 до index = 7 и сравним его с 1. Мы вернем позицию элемента, которая соответствует 1, что равно 6 (index + 1). Следовательно, элемент 1 находится в позиции 6 во входном массиве.

Сложность во времени

Поскольку все элементы массива сравниваются только один раз с входным элементом, следовательно, временная сложность линейного поиска составляет O (N).

Бинарный поиск

Бинарный поиск – это эффективный и часто используемый алгоритм поиска. Этот алгоритм работает только с отсортированными наборами элементов. Поэтому, если данный массив не отсортирован, нам нужно отсортировать его перед применением бинарного поиска.

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

Псевдокод для бинарного поиска

Нижняя граница равна 0, а верхняя граница равна 7. Медиана нижней и верхней границ равна (lower_bound + upper_bound) / 2 = 3. Здесь массив [3] = 4. Значение среднего элемента (4) больше значения значение, которое будет найдено (2). Следовательно, нам не нужно проводить поиск по любому элементу, кроме 4, поскольку элементы за ним, очевидно, будут больше, чем 2.
Поэтому мы опускаем верхнюю границу массива в положение элемента непосредственно перед средним элементом. Теперь мы следуем той же процедуре в том же массиве со следующими значениями,

Теперь нижняя граница равна 0, а верхняя граница равна 2. Медиана нижней и верхней границ равна (lower_bound + upper_bound) / 2 = 1. Здесь array [1] = 2. Поэтому значение среднего элемента соответствует значению поэтому мы возвращаем позицию 2 как 2.

Сложность во времени

Массив для поиска уменьшается наполовину в каждой итерации. Следовательно, временная сложность двоичного поиска составляет O (LogN).

Линейный поиск и бинарный поиск

Линейный поиск – это последовательный поиск, который сканирует по одному элементу за раз. Время, затрачиваемое на поиск данного элемента, увеличивается, если количество элементов в массиве увеличивается.

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

Линейный поиск выполняет сравнение на равенство, тогда как бинарный поиск выполняет сравнение на основе порядка

Заключение

В этой статье мы узнали о линейном поиске и бинарном поиске. Об этом могут спросить на собеседованиях.

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Что мне нужно, так это цикл для каждой записи в Master List и поиск записей с одинаковыми именами в DetailList.

Мой код работает очень медленно, каждый поиск обходится мне в 500 миллисекунд, чтобы завершить его, поэтому при 300 тыс. Записей это займет 2500 минут :( Завершение. Есть ли другой способ ускорить эту функцию? Спасибо и простите за мой плохой английский.

Обновлен код, чтобы сделать его более понятным из того, что я хочу сделать.

3 ответа

Использование некоторой хеш-структуры будет одним из лучших вариантов:

Lookup возвращает пустую последовательность, если ключ отсутствует, поэтому вам не нужно его проверять.

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

Приятно то, что вам нужно только обработать некоторые из MasterRecords (например, после 1000-го вы решаете, что нашли то, что искали), или если у вас есть несколько MasterRecords, для которых вам не нужны все DetailRecords не обрабатывается больше записей, чем необходимо. Linq позаботится об этом


Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.

Алгоритмически это выглядит так:

  1. Запоминаем левую L и правую R границы массива (индексы, а не значения)
  2. Берем индекс M посередине между L и R
  3. Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
  4. Возвращаемся на шаг 2

Таким образом мы на каждом шаге алгоритма сужаем область поиска в 2 раза. Этот алгоритм имеет сложность O(log(n)).

В теории все просто, но на практике возникают проблемы.

Приведу сразу свою реализацию, а потом разберем все проблемы.

Распространенная ошибка реализации — переполнение типа при вычислении середины интервала. Именно поэтому середина вычисляется так

Еще одна проблема — выход из алгоритма. Нужно правильно обрабатывать ситуацию, когда интервал поиска свелся к двум соседним индексам. Я для наглядности вместо хитрых операций с индексами вынес эту ситуацию в отдельный блок кода

Так же можно добавить дополнительную оптимизацию для ситуации, когда value заведомо слишком маленькое или большое. Будут такие проверки в начале метода:

Читайте также: