Бинарный поиск в массивах

Двоичный(бинарный) поиск - алгоритм поиска элемента в отсортированном массиве. Бинарный поиск нашёл себе применение в математике и  информатике. Возможно, Вы не будете пользоваться алгоритмом двоичного поиска, но знать его принцип работы должны. Двоичный поиск можно использовать только в том случае, если есть массив, все элементы которого упорядочены (отсортированы). Бинарный поиск не используется для поиска максимального или минимального элементов, так как в отсортированном массиве эти элементы содержатся в начале и в конце массива соответственно, в зависимости от тога как отсортирован массив, по возрастанию или по убыванию. Поэтому алгоритм бинарного поиска применителен, если необходимо найти некоторый ключевой элемент в массиве. То есть организовать поиск по ключу, где ключ - это определённое значение в массиве. Разработаем программу, в которой объявим одномерный массив, и организуем двоичный поиск.Объявленный массив нужно инициализировать некоторыми значениями, причём так, чтобы эти значения были упорядоченны.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// binary_search.cpp: определяет точку входа для консольного приложения.   #include "stdafx.h" #include <iostream> using namespace std;   int main(int argc, char* argv[]) {     const int size_array = 10;     int array_[size_array] = {-8, -7, -6, -6, -4, 2, 6, 7, 8, 15 }; // объявление одномерного массива     cout << "array[" << size_array << "] = { ";     for (int counter = 0; counter < size_array; counter++)     {      cout << array_[counter] << " "; // печать элементов одномерного массива array1     }     cout << " }";     int average_index = 0, // переменная для хранения индекса среднего элемента массива         first_index   = 0, // индекс первого элемента в массиве         last_index    = size_array -1, // индекс последнего элемента в массиве //--------------------------------------------------------         search_value  = 15; // искомое (ключевое) значение //--------------------------------------------------------     if (last_index == -1) cout << "\narray is empty" << endl; // массив пуст       while (first_index < last_index)     {         average_index = first_index + (last_index - first_index) / 2; // меняем индекс среднего значения         search_value <= array_[average_index] ? last_index = average_index : first_index = average_index + 1;    // найден ключевой элемент или нет      }     if ( array_[last_index] == search_value)         cout << "\nvalue is found" << "\nindex = " << last_index << endl;     else         cout << "\nvalue is not found" << endl;     system("pause");     return 0; }

Итак, в строке 9 объявлена целочисленная переменная константа, которой присвоено значение 10 - размер одномерного массива. Согласно тону хорошего программирования размер статического массива должен задаваться в отдельной переменной, с квалификатором const. В строке 10 объявлен одномерный массив соответствующего размера. Строки 11 - 16 выводят на экран элементы массива с некоторым оформлением. В строках 17 -19 объявляются переменные. которые будут использоваться в алгоритме двоичного поиска В строке 21 объявлена переменная, значение в которой будет искомым. В строка 23 - 33находится алгоритм двоичного поискав массивах. Сначала нужно проверить размер массива, вкотором будет искаться ключевое значение, строка 23. Массив может быть нулевого размера, если размер массива больше или равен 1, тогда начинаем искать ключевое значение. Объявление цикла while строки 25 - 29, в цикле организован поиск значения таким образом, что после выхода из цикла индекс найденного значения сохранится в переменной last_index. В телецикла, строка 28  объявлена условная операция ? : , хотя можно было воспользоваться оператором выбора if else. И наконец, в строках 30 - 33  объявлен оператор условного выбора if else, который определяет, говорит о том, было ли найдено искомое значение или нет.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

/* Рассмотрим пошагово, как именно работает алгоритм двоичного поиска в массивах на псевдокоде: Шаг первый: проверка условия цикла: 0 < 9 - true average_index = 0 + (9 - 0) / 2 = 4, значит средний елемент -4 проверка в условной операции 15 <= (-4) - false значит first_index = 4 + 1 = 5   Шаг второй: проверка условия цикла: 5 < 9 - true average_index = 5 + (9 - 5) / 2 = 7, значит средний елемент 7 проверка в условной операции 15 <= 7 - false значит first_index = 7 + 1 = 8   Шаг третий: проверка условия цикла: 8 < 9 - true average_index = 8 + (9 - 8) / 2 = 8 // значит средний елемент 8 проверка в условной операции 15 <= 8 - false значит first_index = 8 + 1 = 9   Шаг четвёртый: проверка условия цикла: 9 < 9 - false // выходим из цикла при этом значение в переменной last_index не менялось, так как искомое значение в последнем элементе массива */

Так как, алгоритмы сортировки, нам пока не известны, то массив инициализируем вручную, причём обязательно упорядоченно. В строке 21 указываем искомый элемент массива и запускаем программу (см. Рисунок2).

13

Механизм параметров является основным способом обмена информацией между вызываемой и вызывающей функциями. Параметры, перечисленные в заголовке описания функции, называются формальными, а записанные в операторе вызова функции — фактическими (или аргументами).

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

Существует два вида передачи величин в функцию: по значению и по адресу.

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

При передаче по адресу в стек заносятся копии адресов параметров, а функция осуществляет доступ к ячейкам памяти по этим адресам и может изменить исходные значения параметров:

#include <iostream.h>

void f(int i, int* j, int& k);

int main()

{int i = 1, j = 2, k = 3;

cout <<"i j k\n";

cout << i <<' '<< j <<' '<< k <<'\n';

f(i, &j, k);

cout << i <<' '<< j <<' '<< k;

}

void f(int i, int* j, int& k)

{i++; (*j)++; k++;}

Результат работы программы:

i j k

1 2 3

1 3 4

Первый параметр (i) передается по значению. Его изменение в функции не влияет на исходное значение.

Второй параметр (j) передается по адресу с помощью указателя, при этом для передачи в функцию адреса фактического параметра используется операция взятия адреса, а для получения его значения в функции требуется операция разыменования.

Третий параметр (k) передается по адресу с помощью ссылки.

При передаче по ссылке в функцию передается адрес указанного при вызове параметра, а внутри функции все обращения к параметру неявно разыменовываются. Поэтому использование ссылок вместо указателей улучшает читаемость программы. Использование ссылок вместо передачи по значению более эффективно, поскольку не требует копирования параметров.

Если требуется запретить изменение параметра, используется модификатор const:

int f(const char*);

char* t(char* a, const int* b);

СОВЕТ

Рекомендуется указывать const перед всеми параметрами, изменение которых в функции не предусмотрено. Это облегчает отладку. Кроме того, на место параметра типа const& может передаваться константа.

Параметры, передаваемые в функцию, могут быть любого типа (например, вещественного, структурой, перечислением, объединением, указателем), кроме массива или функции, которые передаются с помощью указателей.

Передача массивов в качестве параметров

Массив всегда передается по адресу. При этом информация о количестве элементов массива теряется, и следует передавать его размерность через отдельный параметр (если размерность массива является константой, проблем не возникает, поскольку можно указать ее и при описании формального параметра, и в качестве границы циклов при обработке массива внутри функции).

:

#include <iostream.h>

int sum(const int* mas, const int n);

int const n = 10;

void main(){

int marks[n]={3, 4, 5, 4, 4};

cout << "Сумма элементов массива: " << sum(marks, n);

}

int sum(const int* mas, const int n) /*варианты: int sum(int mas[], int n) или int sum(int mas[n], int n)

(n должна быть константой) */

{int s = 0;

for (int i = 0 ; i<n; i++) s += mas[i];

return s;}

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

Внутри функции массив интерпретируется как одномерный, а его индекс пересчитывается в программе. В приведенном ниже примере с помощью функции подсчитывается сумма элементов двух двумерных массивов. Размерность массива b известна на этапе компиляции, под массив a память выделяется динамически:

#include <stdio.h>int sum(const int *a, const int nstr, const int nstb);void main(){

int b[2][2] = {{2, 2}, {4, 3}};

printf("b %d\n", sum(&b[0][0], 2, 2)); /* имя массива передавать нельзя из-за несоответствия типов */

int i, j, nstr, nstb, *a; printf("Введите количество строк и столбцов: \n");

scanf("%d%d", &nstr, &nstb);

a = (int *)malloc( nstr*nstb*sizeof(int) );

for (i = 0; i<nstr; i++)

for (j = 0; j<nstb; j++)scanf("%d", &a[i*nstb+j]);

printf("a %d\n", sum(a, nstr, nstb));

}

int sum(const int *a, const int nstr, const int nstb)

{int i, j, s = 0;

for (i = 0; i<nstr; i++)

for (j = 0; j<nstb; j++)s += a[i*nstb + j];

return s;}

Для того чтобы работать с двумерным массивом естественным образом, можно применить альтернативный способ выделения памяти:

#include <iostream.h>int sum(const int **a, const int nstr, const int nstb);

void main(){int nstr, nstb;

cin >> nstr >> nstb;

int **a;

a = new int* [nstr];

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

a[i] = new int [nstb];

/* ... формирование матрицы a */

cout << sum(a, nstr, nstb);

}

int sum(const int **a, const int nstr, const int nstb)

{int i, j, s = 0;

for (i = 0; i<nstr; i++)

for (j = 0; j<nstb; j++)s += a[i][j];

return s;}

В этом случае память выделяется в два этапа: сначала под столбец указателей на строки матрицы, а затем в цикле под каждую строку. Освобождение памяти выполняется в обратном порядке.

Передача имен функций в качестве параметров

Функцию можно вызвать через указатель на нее. Для этого объявляется указатель соответствующего типа и ему с помощью операции взятия адреса присваивается адрес функции:

void f(int a ){ /* ... */ }//определение функции

void (*pf)(int);//указатель на функцию

...

pf = &f;/* указателю присваивается адрес функции (можно написать pf = f;) */

pf(10);/* функция f вызывается через указатель pf (можно написать (*pf)(10) ) */

Для того чтобы сделать программу более читаемой, при описании указателей на функции используют переименование типов (typedef). Можно объявлять массивы указателей на функции (это может быть полезно, например, при реализации меню):

typedef void (*Pf)(int);/* описание типа PF как указателя на функцию с одним параметром типа int */

PF menu[]={&new, &open, &save}/* описание и инициализация массива указателей */

menu[1](10);//вызов функции open

Указатели на функции передаются в подпрограмму таким же образом, как и параметры других типов:

void fun(PF pf)/* функция fun получает в качестве параметра указатель типа PF */

{... pf(10); ...}//вызов функции, переданной через указатель

Тип указателя и тип функции, которая вызывается посредством него, должны совпадать в точности.

Параметры со значениями по умолчанию

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

int f(int a, int b = 0);

void f1(int, int = 100, char* = 0);

void err(int errValue = errno);//errno — глобальная переменная

f(100); f(a, 1);// варианты вызова функции f

f1(a); f1(a, 10); f1(a, 10, "Vasia");// варианты вызова функции f1

f1(a,,"Vasia") // неверно!

№16

16.2. Потоковый ввод/вывод в C++

Ввод/вывод в C++ осуществляется с помощью потоков библиотеки C++, доступных при подключении заголовочного файла iostream.h (в VC++.NET – объекта-заголовкаiostream). Поток представляет собой объект какого-либо потокового класса.

Потоковые классы сконструированы на основе базового класса ios:

ios – базовый потоковый класс;

istream – класс входных потоков;

ostraem – класс выходных потоков;

iostream – класс двунаправленных потоков ввода/вывода.

В потоковые классы включены операторы добавления данных в поток << и извлечения данных из потока >>.

На основе класса istream в библиотеке C++ объявлен объект-поток cin, представляющий собой стандартный буферизованный входной поток, связанный обычно с клавиатурой консоли. Извлечение данных из потока имеет следующую форму записи:

int a;

float b;

cin >> a >> b;

где a и b – переменные заданного типа, в которые помещаются данные из потока cin.

В роли разделителей значений в потоке используются пробельные символы (пробел, знак табуляции, перевод строки), поэтому для ввода данных с помощью cin при выполнении программы следует ввести с клавиатуры значения следующими способами:

34 5.78 Enter

или

34 Enter 5.78 Enter

Ввод данных в поток завершается нажатием клавиши Enter. Если количество заполняемых переменных меньше, чем количество значений в потоке, из потока извлекается столько значений, сколько переменных надо заполнить, а остальные значения сохраняются в потоке и будут прочитаны при следующем извлечении данных из потока.

На основе класса ostream объявлен объект-поток cout, представляющий собой стандартный буферизованный выходной поток, связанный обычно с дисплеем консоли.

Форма записи добавления данных в поток следующая:

cout << a << b;

при этом значения переменных a и b выводятся на экран без разделителя и в формате, заданном по умолчанию. Перемещение курсора на следующую строку экрана после вывода данных не происходит.

Для перевода курсора на новую строку используется манипулятор endl:

cout << a <<" "<< b << endl;

В этом примере значения переменных a и b на экране разделены пробелом, после вывода данных происходит переход на новую строку, а сами значения выводятся на экран в виде, соответствующем их типу: 34 5.78.

Для потока cin определен специальный метод для ввода символов – getline(Str,Count), позволяющий в строковую переменную Str ввести из потока заданное количество символов (Count−1):

char str1[128];

cout <<"STR1-->";

cin.getline(str1,9);

cout << str1 << endl;

Если при выполнении этого фрагмента программы ввести с клавиатуры последовательность символов abcdefghj, в переменную str1 будут помещены 8 символов и символ'\0', а на экране появится строка abcdefgh.

В потоках cin и cout можно форматировать данные, для этого используются специальные манипуляторы, доступные через заголовочный файл iomanip.h.

Пример

Форматирование вывода в потоке cout:

#include <iostream.h>

#include <iomanip.h>

int main(void)

{

//Выравнивание по левому краю – left, по правому краю – right

cout.setf(ios_base::left);

//Вывод с плавающей точкой – scientific, с фиксированной – fixed

cout.setf(ios_base::scientific);

//Точность вывода числа на экране

cout << setprecision(3);

double x=2.5,y=125.76435;

//Ширина поля вывода числа – 15 знаков

cout << setw(15) << x << setw(15) << y << endl;

return 0;

}