Поиск в массивах. Линейный поиск и двоичный поиск.

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

Линейный поиск (рис.4.19) сравнивает каждый элемент массива с ключомпоиска. Так как массив не упорядочен, то в среднем, программа должна сравнить с ключом поиска половину элементов массива.

Метод линейного поиска хорошо работает для небольших или для несортированных массивов. Для больших массивов линейный поиск неэффективен. Если массив отсортирован, можно использовать метод двоичного поиска.

Алгоритм двоичного поиска (рис.4.20) исключает половину еще непроверенных элементов массива после каждого сравнения. Алгоритм определяет местоположение среднего элемента массива и сравнивает его с ключом поиска. Если они равны, то ключ поиска найден и выдается индекс этого элемента. В противном случае задача сокращается на половину элементов массива. Если ключ поиска меньше, чем средний элемент массива, то дальнейший поиск осуществляется в первой половине массива (если массив был упорядочен по возрастанию), а если больше, то во второй половине. Поиск продолжается до тех пор, пока ключ поиска не станет равным среднему элементу или пока оставшийся подмассив содержит хотя бы один элемент, не равный ключу поиска.

В наихудшем случае двоичный поиск в массиве из 1024 элементов потребует только 10 сравнений.

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

Массивы в С++ могут иметь много индексов. Обычным представлением многомерных массивов являются таблицы значений, содержащие информацию в строках и столбцах. Чтобы определить отдельный табличный элемент, нужно указать два индекса: первый (по соглашению) указывает номер строки, а второй (по соглашению) указывает номер столбца. Таблицы или массивы, которые требуют двух индексов для указания отдельного элемента, называются двумерными массивами. Компиляторы С++ поддерживают по меньшей мере 12-мерные массивы.

На рис.4.21 показан двумерный массив а. Каждый элемент массива а определяется именем элемента в форме a[i] [j].

a– это имя массива, iиj– индексы, которые однозначно определяют каждый элемент в а.

Многомерные массивы могут получать начальные значения в своих объявлениях. Например, двумерный массив b[2] [2]можно объявить и дать ему начальные значения с помощью оператора

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

или

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

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

Рис.4.22демонстрирует присваивание начальных значений двумерным массивам в объявлении.

Размерность первого индекса многомерного массива можно не указывать, но все последующие размерности индексов необходимы.

// рис.4.22

#include "stdafx.h"

#include <iostream>

using namespace std;

void printArray(int [][3]);

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

{

int array1 [2][3]= {{1,2,3},{4,5,6}},

array2 [2][3]= {1,2,3,4,5},

array3 [2][3]={{1,2},{4}};

setlocale(LC_ALL, "rus");

cout<<"Значение массива array1 по строкам:"<<endl;

printArray(array1);

cout<<"Значение массива array2 по строкам:"<<endl;

printArray(array2);

cout<<"Значение массива array3 по строкам:"<<endl;

printArray(array3);

return 0;

}

void printArray(int a[][3])

{

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

{

for(int j=0;j<=2; j++)

cout<< a[i][j]<<" ";

cout<<endl;

}

}