Библиотека функций поиска в массивах

/*

Функции поиска в массивах

*/

#pragma once

#include "stdafx.h"

//

// Прототипы функций

//

int Find1_1(int A[], int n, int Val);

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 1)

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

int Find1_2(int A[], int n, int Val);

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 2)

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

int Find2(int A[], int n, int Val);

// Бинарный поиск значения Val в отсортированном по возрастанию массиве А из n целых значений

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

//

// Реализация

//

int Find1_1(int A[], int n, int Val)

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 1)

{

int i = 0;

while (i < n)

{

if (A[i] == Val)

return i;

++i;

}

return -1;

}

int Find1_2(int A[], int n, int Val)

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 2)

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

{

for (int i = 0; i < n; ++i)

if (A[i] == Val)

return i;

return -1;

}

int Find2(int A[], int n, int Val)

// Бинарный поиск значения Val в отсортированном по возрастанию массиве А из n целых значений

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

{

if ((Val < A[0]) || (Val > A[n - 1])) // Отсеиваем заведомо не входящие в массив значения

return -1;

int a = 0, b = n - 1, c;

while (b >= a)

{

c = (a + b) / 2; // Находим в интервале [а, b] индекс срединного элемента - с

if (Val > A[c]) // Искомое значение справа от с

a = c + 1; // Заменяем левую границу интервала поиска

else

if (Val < A[c]) // Искомое значение слева от с

b = c - 1; // Заменяем правую границу интервала поиска

else // Val == A[c]

return c; // Индекс искомого элемента - с

}

return -1;

}

Программа для проверки функций поиска в массивах:

/*

Find.cpp: определяет точку входа для консольного приложения.

Заголовочные файлы arr_common.h, arr_sort.h и my_rand.h должны находиться в папке этого проекта, либо путь к ним должен быть указан в настройках параметров проекта:

Меню среды: Проект – Свойства – Свойства конфигурации – Каталоги VC++ - Каталоги включения и добавляем здесь путь к нашим заголовочным файлам

*/

#include "stdafx.h"

#include <iostream>

#include <conio.h>

#include "arr_common.h"

#include "arr_sort.h"

#include "arr_find.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(0, "");

const int N = 1000;

int M[N], V, Ind;

setlocale(0, "");

RandInit(); // Инициализируем датчик случайных чисел (#include "my_rand.h")

cout << " Проверка алгоритма бинарного поиска.\n";

cout << " ------------------------------------\n";

RandMakeArr(M, N, 1, 1000); // Заполняем массив случайными чиселами (#include "my_rand.h")

Sort2(M, N, 1); // Сортируем массив М из N элементов (#include "arr_sort.h")

ArrOut(M, N); // Выводим отсортированный массив на экран

for (char b = '1'; b != 27; cout << "\n\t\t\tПродолжим? (нет - Esc)",

b = _getch(), cout << endl)

{

cout << "\nКакое значение надо найти? ";

cin >> V; // Вводим значение для поиска

Ind = Find2(M, N, V); // Поиск V в массиве М из N элементов бинарным поиском

if (Ind != -1)

cout << "Индекс значения " << V << " равен " << Ind << endl;

else

cout << "Значение " << V << " не найдено" << endl;

}

return 0;

}