Приветствую всех, сегодня рассмотрим несколько алгоритмов поиска. Поиск часто встречается в приложениях с работой текстами или базами данных, и частенько приходиться их применять. Вариаций поисков много, при реализации их стоит учитывать некоторые специфические моменты. А так же скорость работы этих методов.
Алгоритм Бинарный поиск:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
static int FindIndexByBinarySearch(int[] array, int element) { var left = 0; var right = array.Length - 1; while (left < right) { var middle = (right + left) / 2; if (element <= array[middle]) right = middle; else left = middle + 1; } if (array[right] == element) return right; return -1; } public static void Main() { var array = new[]{1,2,3,4,5,5,5,6}; Console.WriteLine(FindIndexByBinarySearch(array, 5)); } |
Разберем код, мы создаем целочисленный массив со значениями и передаем его в метод FindIndexByBinarySearch в методе происходит вычисление, результат который возвращает индекс найденного числа в метод Main, однако если число не будет найдено вернет -1. Суть метода сводиться к тому, что массив чисел делиться по индексу на 2, до тех пор пока не останется один элемент, который сравнивается с заданным числом и если они равны выводиться результат.
Алгоритм Линейный поиск:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
static int FindIndex(int[] array, int element) { for (int i = 0; i < array.Length; i++) if (array[i] == element) return i; return -1; } static int FindIndex(string[] array, string element) { for (int i = 0; i < array.Length; i++) if (array[i] == element) return i; return -1; } |
Разберем код алгоритма линейного поиска, у нас два метода, которые принимают один из них массив строк другой массив чисел и у каждого метода элемент поиска. Внутри метода имеется цикл for который производит по элементную сверку с заданным элементом в метод, в случаи если элемент найден, то будет выполнен return с найденным элементом, если искомый элемент не найден соответственно выполнен return который вернет -1. Линейный поиск алгоритма хорош тем что его можно реализовать как с цифрами, так и символами и строками, один не достаток его в том что если передать большой объем массива, то этот код может быть выполнятся длительное время и это стоит учитывать.