Стоит только посадить Германию в седло, а уж поскакать она сумеет (О. Бисмарк).

Алгоритмы поиска в C #

3 мин для чтения
FavoriteLoadingДобавить в избранное
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...
28 января 2019
Алгоритмы поиска в C #

Вступление

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

  1. Линейный поиск
  2. Бинарный поиск

Алгоритм поиска пути из точки А в точку Б на C# — одна из самых распространенных задач при разработке игр. Для решения этой задачи есть множество алгоритмов, но самым часто используемым является A* (A star).
Мы будем объяснять алгоритмы с помощью примера.

 

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

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

 

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

procedure LinearSearch(array, value)  
  
   foreach item in array  
      if item == value    
         return the item's index    
      end if    
   end foreach      
   return -1  
  
end procedure

 

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

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

Алгоритмы поиска в C #

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

 

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

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

 

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

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

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

 

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

Procedure BinarySearch(array,value)  
  
   Set lowBound = 1  
   Set uppBound = size of array   
  
   while (lowBound <= uppBound)      
      set midPoint = (lowBound + uppBound ) / 2        
       if array[midPoint] > value  
         set uppBound = midPoint - 1             
       else if array[midPoint] < value  
         set lowBound = midPoint + 1           
       else return midPoint  
   end while  
     
   return -1;     
     
end procedure

 

Позвольте нам понять это с помощью примера.
Ссылаясь на изображение ниже; если нам нужно найти позицию 2 в данном массиве, используя бинарный поиск,Алгоритмы поиска в C #

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

Алгоритмы поиска в C #

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

 

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

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

 

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

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

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

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

 

Заключение

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

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

Просмотров: 17

Если статья понравилась, то поделитесь ей в социальных сетях:

Добавить комментарий

Войти с помощью: 

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить
galka

Спасибо! Ваша заявка принята

close
galka

Спасибо! Ваша заявка принята

close