Другое

Способы поиска элемента в массиве С: просто о сложном

Поиск в массиве предусмотрен во многих языках программирования, в том числе и в С. Поиск является видом обработки данных в массиве с целью определения и выявления элемента, который соответствует заданным критериям. Поиск в массиве элемента на С разделяют на 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. Допустим, у вас есть отсортированный массив с простыми числами от 1 до 10: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

  2. Вам необходимо найти индекс значения числа «2». «2» будет ключом поиска, поэтому на первом этапе массив поделится «пополам». Так как индексирование элементов в массиве начинается с 0, у нас получается, что 0 + 9 / 2 = 4 (0,5 отбрасывается, и индекс округляется). Под индексом 4 у нас стоит число 5, это число сравнивается с нашим ключом. 5 не равно 2 и больше него. Если бы «среднее» значение массива совпало с ключом, тогда массив бы прекратил работу.

  3. Так как 5 больше 2, поиск значения продолжится в части массива, содержащей числа от 1 до 5, а числа от 6 до 10 «отбрасываются в сторону». Вторым шагом алгоритма будет поиск среднего значения в «укороченном» массиве: 0 + 4 / 2 = 2. Под индексом 2 у нас расположено число 3. 3 сравнивается с ключом. Алгоритм определит, что 3 не равно 2 и больше него. Значит, будет третий шаг.

  4. На третьем шаге еще часть массива после числа 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 элемента. Если и в этом случае искомый элемент не будет найден, тогда его нет в массиве.

Заключение

Поиск элемента в массиве С можно осуществить и другими алгоритмами, например, используя:

  • «Решето Эратосфена»;

  • поиск с «барьером»;

  • и другие алгоритмы.

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

Схожие статьи

Игровой движок на C: какой выбрать и можно ли написать собственный?
Другое

Игровой движок на C: какой выбрать и можно ли написать собственный?

Cosmos: операционная система, ее требования и пошаговая установка
Другое

Cosmos: операционная система, ее требования и пошаговая установка

Другое

Что такое сетевой нейтралитет и зачем он нужен

Новая атака на Фейсбук. Как избежать потери аккаунта и средств?
Другое

Новая атака на Фейсбук. Как избежать потери аккаунта и средств?