Поиск
Ничто не сравнится с массивом, если нам нужно хранить статические табличные данные. Инициализация во время компиляции делает задачу конструирования таких массивов простой и легкой. (В Java инициализация происходит во время выполнения, но это можно считать незначительной деталью реализации, пока массивы не слишком велики.) В программе для распознания слов, слишком часто употребляемых в плохой прозе, мы можем написать:
Функция поиска должна знать, сколько в массиве элементов. Один из способов сообщить ей это – передать длину массива в виде аргумента; второй способ, использованный здесь, – поместить в конце массива элемент-маркер NULL:
В С и C++ для передачи в качестве параметра массив строк можно описать как char *array[ ] или char **array. Эти две формы эквивалентны, но в первой сразу видно, как будет использоваться параметр.
Предлагаемый поисковый алгоритм называется последовательным, поиском, потому что он просматривает по очереди все элементы, сравнивая их с искомым. Когда данных немного, последовательный поиск работает достаточно быстро. Есть стандартные библиотечные функции, которые выполняют последовательный поиск для определенных типов данных. Например, в языках С и C++ функции strch г и strstr ищут первое вхождение заданного символа или подстроки в строку, в Java у класса String есть метод indexOf, а обобщенные функции поиска в C++ find применимы к большинству типов данных. Если такая функция существует для нужного вам типа данных, то используйте ее.
Последовательный поиск достаточно прост, но время его работы прямо пропорционально количеству данных, которые нужно просмотреть; удвоение количества элементов приведет к удвоению времени на поиск, если искомого элемента в массиве нет. Это линейное соотношение (время выполнения является линейной функцией от размера данных), поэтому такой метод также называется линейным поиском.