Проверка наличия значения в массиве

Если массив не отсортирован, то проверка наличия значения в массиве сводится к перебиранию всех элементов от начала до конца. При наличии первого вхождения можно прервать поиск. Пример поиска первого вхождения приведен в листинге 6.5.

Листинг 6.5. Поиск первого вхождения элемента

#include <iostream>
#include <clocale>

int main() {
   std::setlocale(LC_ALL, "Russian_Russia.1251");
   const int ARR_SIZE = 5;
   int arr[ARR_SIZE] = {10, 5, 6, 1, 3}, index = -1;
   int search_key = 6;
   for (int i = 0; i < ARR_SIZE; ++i) {
      if (arr[i] == search_key) {
         index = i;
         break;
      }
   }
   if (index != -1) {
      std::cout << "index = " << index << std::endl;
   }
   else std::cout << "Элемент не найден" << std::endl;
   return 0;
}

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

Поиск по отсортированному массиву производится гораздо быстрее, так как не нужно каждый раз просматривать все значения массива. Наиболее часто применяется бинарный поиск (листинг 6.6), при котором массив делится пополам и производится сравнение значения элемента, расположенного в середине массива, с искомым значением. Если искомое значение меньше значения элемента, то пополам делится первая половина массива, а если больше, то пополам делится вторая половина. Далее таким же образом производится деление оставшейся части массива. Поиск заканчивается когда будет найдено первое совпадение или когда начальный индекс станет больше конечного индекса. Таким образом, на каждой итерации отбрасывается половина оставшихся элементов. Поиск значения, которое расположено в конце массива, состоящего из 100 000 элементов, будет произведен всего за 17 шагов. Однако, если поиск производится один раз, то затраты на сортировку сведут на нет все преимущества бинарного поиска. В этом случае прямой перебор элементов может стать эффективнее.

Листинг 6.6. Бинарный поиск в отсортированном массиве

#include <iostream>
#include <cstdlib>
#include <clocale>

int compare(const void *arg1, const void *arg2);
int search(int key, const int *arr, int count);

int main() {
   std::setlocale(LC_ALL, "Russian_Russia.1251");
   const int ARR_SIZE = 5;
   int arr[ARR_SIZE] = {10, 5, 6, 1, 3};
   // Сортируем по возрастанию
   std::qsort(arr, ARR_SIZE, sizeof(int), compare);
   // Производим поиск
   int index = search(6, arr, ARR_SIZE);
   if (index != -1) {
      std::cout << "index = " << index << std::endl;
   }
   else std::cout << "Элемент не найден" << std::endl;
   return 0;
}
// Сортировка по возрастанию
int compare(const void *arg1, const void *arg2) {
   if (*(int *)arg1 < *(int *)arg2) return -1;
   if (*(int *)arg1 > *(int *)arg2) return 1;
   return 0;
}
// Бинарный поиск в отсортированном массиве
int search(int key, const int *arr, int count) {
   if (count < 1 || !arr) return -1;
   int start = 0, end = count - 1, i = 0;
   while (start <= end) {
      i = (start + end) / 2;
      if (arr[i] == key) return i;
      else if (arr[i] < key) start = i + 1;
      else if (arr[i] > key) end   = i - 1;
   }
   return -1;
}

Для проверки наличия элемента в массиве можно также воспользоваться стандартной функцией bsearch(). Прототип функции:

#include <cstdlib> /* или #include <stdlib.h> */
void *bsearch(const void *key, const void *base, 
              size_t numOfElements, size_t sizeOfElements,
              int (*PtFuncCompare)(const void *, const void *));

В параметре key передается адрес переменной, в которой хранится искомое значение, в параметре base указывается адрес первого элемента массива, в параметре numOfElements — количество элементов массива, а в параметре sizeOfElements — размер каждого элемента в байтах. Адрес пользовательской функции (указывается название функции без круглых скобок и параметров), внутри которой производится сравнение двух элементов, передается в последнем параметре. Прототип пользовательской функции сравнения должен выглядеть так:

int <Название функции>(const void *arg1, const void *arg2);

Функция должна возвращать отрицательное значение, если arg1 меньше arg2, положительное значение, если arg1 больше arg2, или 0, если значения равны. Внутри функции необходимо выполнить приведение указателя void * к определенному типу. Кроме того, необходимо выполнить приведение указателя при получении результата. Если значение не найдено, то возвращается нулевой указатель, в противном случае указатель ссылается на найденный элемент. Пример использования функции bsearch() приведен в листинге 6.7.

Листинг 6.7. Проверка наличия значения в массиве с помощью функции bsearch()

#include <iostream>
#include <cstdlib>
#include <clocale>

int compare(const void *arg1, const void *arg2) {
   if (*(int *)arg1 < *(int *)arg2) return -1;
   if (*(int *)arg1 > *(int *)arg2) return 1;
   return 0;
}

int main() {
   std::setlocale(LC_ALL, "Russian_Russia.1251");
   const int ARR_SIZE = 5;
   int arr[ARR_SIZE] = {10, 5, 6, 1, 3}, search_key = 6;
   // Сортируем по возрастанию
   std::qsort(arr, ARR_SIZE, sizeof(int), compare);
   // Производим поиск
   int *p = (int *)std::bsearch(&search_key, arr, ARR_SIZE, 
                                 sizeof(int), compare);
   if (p) {
      int index = (int) (p - arr);
      std::cout << "index = " << index << std::endl;
   }
   else std::cout << "Элемент не найден" << std::endl;
   return 0;
}
На заметку

Учебник C++ (MinGW-W64)
Учебник C++ (MinGW-W64) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов