Поиск в массиве предусмотрен во многих языках программирования, в том числе и в С. Поиск является видом обработки данных в массиве с целью определения и выявления элемента, который соответствует заданным критериям. Поиск в массиве элемента на С разделяют на 2 большие категории:
поиск в несортированном массиве;
поиск в сортированном массиве.
То есть поиск и сортировка в массиве идут тесно рядом. Сортировкой называют специальный процесс, при котором элементы в массиве переставляются по какому-либо критерию или свойству. Например, если в массиве содержатся цифровые данные, то можно осуществить сортировку по возрастанию или убыванию, — это приведет к тому, что элементы в массиве будут располагаться упорядоченно. Главная цель любой сортировки — облегчить работу с элементами массива, например облегчить поиск в массиве.
Поиск элемента в массиве на С
Поиск в массиве на С можно осуществить несколькими методами, каждый из которых отличается своими характеристиками. На сегодня существует достаточно много разнообразных алгоритмов поиска, самыми распространенными из них являются:
линейный поиск в массиве на С;
двоичный или бинарный поиск в массиве на С;
интерполирующий поиск на С.
Есть и другие методы, но, если изучить эти — их будет вполне достаточно, чтобы найти нужный элемент в массиве.
Линейный поиск элемента в массиве на С
Линейный поиск в массиве на С является самым простым алгоритмом, поэтому изучается первым. Суть его заключается в том, что необходимо будет «перебирать» все элементы массива на совпадение с заданными критериями или ключами. Самый простой не означает самый быстрый. Этот вид поиска очень затратный по времени, поэтому не рекомендуется к применению в массивах с большим количеством данных.
Пример функции линейного поиска:
int linSearch(int arr[], int requiredKey, int arrSize)
{
for (int i = 0; i < arrSize; i++)
{
if (arr[i] == requiredKey)
return i;
}
return -1;
}
Данный вид поиска подходит для поиска одиночного элемента в небольших несортированных массивах. Если массив большой, тогда лучше отсортировать его и применить один из методов, описанных ниже.
Двоичный или бинарный поиск элемента в массиве на С
Бинарный поиск в массиве на С подходит для отсортированных массивов. Он также считается довольно простым, но при этом более эффективным, чем линейный алгоритм. Алгоритм его работы основывается на делении массива «пополам» и сверки среднего значения с заданным ключом. Например:
Допустим, у вас есть отсортированный массив с простыми числами от 1 до 10: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
Вам необходимо найти индекс значения числа «2». «2» будет ключом поиска, поэтому на первом этапе массив поделится «пополам». Так как индексирование элементов в массиве начинается с 0, у нас получается, что 0 + 9 / 2 = 4 (0,5 отбрасывается, и индекс округляется). Под индексом 4 у нас стоит число 5, это число сравнивается с нашим ключом. 5 не равно 2 и больше него. Если бы «среднее» значение массива совпало с ключом, тогда массив бы прекратил работу.
Так как 5 больше 2, поиск значения продолжится в части массива, содержащей числа от 1 до 5, а числа от 6 до 10 «отбрасываются в сторону». Вторым шагом алгоритма будет поиск среднего значения в «укороченном» массиве: 0 + 4 / 2 = 2. Под индексом 2 у нас расположено число 3. 3 сравнивается с ключом. Алгоритм определит, что 3 не равно 2 и больше него. Значит, будет третий шаг.
На третьем шаге еще часть массива после числа 3 «отбрасывается». Алгоритм ищет среднее значение в оставшихся индексах: 0 + 2 / 2 = 1. Под индексом 1 у нас располагается число 2, это число сравнивается с нашим ключом. Алгоритм определяет, что число 2 равно нашему ключу 2, выдает нам соответствующий индекс числа и заканчивает свою работу.
Вот как все, что мы описали выше, выглядит в скрипте:
#include <iostream>
using namespace std;
int SearchingAlgorithm (int arr[], int left, int right, int keys)
{
int middle = 0;
while (1)
{
middle = (left +right) / 2;
if (keys < arr[middle])
right = middle -1;
else if (keys > arr[])
left = middle + 1;
else
return middle;
if (left > right)
return -1;
}
}
int main()
{
selocale (LC_ALL, “rus“);
const int SIZE = 10;
int array[SIZE] = {};
int keys = 0;
int index = 0;
for (int i = 0; i < SIZE; i++)
{
array[i] = i +1;
cout < < array[i] < < “ | “;
cout < < “\n\n Необходимо ввести числовое значение для поиска: “;
cin > > keys;
index = SearchingAlgorithm (array, 0, SIZE, keys);
if (index >= 0)
cout < < “Значение, которое вы указали, располагается с порядковым индексом: “ < < index < < “\n\n“;
else
cout < < “Введенное значение в массиве не обнаружено!\n\n“;
return 0;
}
Если запустить программу, тогда получится следующий результат:
Необходимо ввести числовое значение для поиска: 2
Значение, которое вы указали, располагается с порядковым индексом: 1
Поиск в массиве С бинарным алгоритмом хорош тем, что он работает намного быстрее, чем линейный алгоритм. Представим, что вам необходимо осуществить поиск в массиве, содержащем 1000 элементов. Линейный поиск должен будет обойти все элементы, а бинарный — около 10. Такой результат возможен, потому что при каждом определении среднего значения часть массива, где точно нет искомого значения, просто отсеивается. Например, при первом шаге в массиве с 1000 элементов 500 отсеются, при втором — еще 250 и т. д.
Самая главная проблема бинарного поиска заключается в том, что он работает только в отсортированных и упорядоченных массивах.
Интерполирующий поиск элемента в массиве С
Интерполирующий поиск пришел из математики, и он не настолько сложен, как произносится. Его смысл сводится к тому, что необходимо определять область поиска заданного значения, вычисляя подобие расстояний между искомым элементом и всей областью. Как это выглядит в коде:
#include <iostream>
using namespace std;
int main ()
{
//Определяем массив со значениями, среди которых будет проходить поиск
int OwnArray [] {2, 3, 5, 7, 8, 90, 124, 232, 1001, 1236 };
int y = 0; //определяем текущую позицию массива
int c = 0; //определяем левую границу массива, откуда будет начинаться поиск
int d = 9; //определяем правую границу массива, докуда будет продолжаться поиск
int WeSearch = 124; //определяем элемент, который ищем
bool found;
//Запускаем интерполяционный поиск в массиве С
for (found = false; (OwnArray[c] < WeSearch) && (OwnArray[d] > WeSearch) && | found;)
y = c + ((WeSearch — OwnArray[c]) * (d — c)) / (OwnArray[d] — OwnArray[c]);
if (OwnArray[y] < WeSearch)
c = y +1;
else if (OwnArray[y] > WeSearch)
d = y -1;
else
found = true;
}
//интерполяционный поиск в массиве окончен, тогда можно вывести результаты
if (OwnArray[c] == We Search)
cout < < WeSearch < < “Элемент найден“ < < c < < endl;
else if (OwnArray[d] == WeSearch)
cout < < WeSearch < < “Элемент найден“ < < d < < endl;
else
cout < < “Извините, элемент не найден“ < < endl;
return 0;
}
Простыми словами: этот метод вычисляет область, где может быть расположен искомый элемент; если в этой области нет элемента, тогда границы области в массиве сдвигаются в ту или иную сторону. Этот метод чем-то похож на бинарный алгоритм, потому что в нем также «куски» массива постепенно отсеиваются, пока искомая область не будет сужена до 1 элемента. Если и в этом случае искомый элемент не будет найден, тогда его нет в массиве.
Заключение
Поиск элемента в массиве С можно осуществить и другими алгоритмами, например, используя:
«Решето Эратосфена»;
поиск с «барьером»;
и другие алгоритмы.
Каждый из них по-своему хорош, но описанных выше алгоритмов достаточно для понимания стратегии поиска. Ведь даже их можно модифицировать по-своему, адаптируя под собственную задачу.
Другое
