Двоичный поиск в упорядоченном массиве

Рассмотрим теперь, как реализовать быстрый поиск, используя упорядоченность массива; для определенности будем считать, что массив отсортирован по возрастанию. Главное свойство упорядоченного массива, позволяющее осуществить эффективный поиск, заключается в том, что, если искомый элемент меньше некоторого элемента массива, то можно отбросить расположенную справа от этого элемента часть массива и продолжать поиск только по левой части. Отсюда получается следующий алгоритм. Выбрать элемент, расположенный в середине массива, и сравнить искомый элемент с ним. Если элемент окажется меньше, то выбрать середину левой части и осуществлять деление до тех пор, пока не будет равенства или массив будет состоять из одного элемента. Если он не равен, то такого элемента нет в массиве.

printf("Введите искомый элемент: ");

int x;

scanf("%d",&x);

int left = 0;

int right = size-1;

bool found = false;

while (left<=right) {

int center = left + (right-left)/2;

if (x == numbers[center]) {

found = true;

break;

} else if (x < numbers[center]) {

right = center - 1;

} else {

left = center + 1;

}

}

if (found) {

printf("Элемент %d найден\n",x);

} else {

printf("Элемент %d не найден\n",x);

}

Многомерные массивы

Рассмотренные нами массивы являются одномерными, другими словами, каждый элемент в таких массивах определяется одним индексом. По аналогии можно вспомнить, что точка на прямой задается одной координатой. Прямая – это одномерное пространство. Существует также плоскость – двумерное пространство или даже трехмерное пространство. В математике вообще существуют пространства любой размерности. Аналогична ситуация и с массивами – они могут быть двумерными, трехмерными и так далее. Элементами одномерного массива являются элементы базовых типов, элементами двумерных массивов являются одномерные массивы, элементами трехмерных - двумерные и т.д. Следовательно, двумерный массив может рассматриваться как массив, элементы которого определяются двумя индексами, трехмерный – тремя и т.д. При объявлении многомерного массива нужно указать все его размеры, которые не обязательно должны быть одинаковыми:

int array_1d[100];

float array_2d[100][200];

char array_3d[100][200][50];

double array_4d[100][200][50][10];

unsigned short array_5d[100][200][50][10][30];

Обращение к элементам происходит так:

printf("%d", array_1d[i]);

printf("%f", array_2d[i][j]);

printf("%c", array_3d[i][j][k]);

printf("%e", array_4d[i][j][k][l]);

printf("%d", array_5d[i][j][k][l][m]);