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

Двоичный поиск исключает половину элементов массива после каждого сравнения. Алгоритм выделяет средний элемент массива и сравнивает его с ключом поиска. Если они равны, ключ поиска найден и возвра-пдается индекс массива этого элемента. В противном случае задача поиска сокрапдается на половину массива.

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

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

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

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

Терминология

а [ i ]

а [ i ] [ j ]

временная область для обмена значений выход за пределы массива двоичный поиск в массиве двумерный массив значение элемента именованная константа имя массива индекс

индекс столбца индекс строки квадратные скобки [ ] ключ поиска

линейный поиск в массиве

массив

массив m на п масштабируемость многомерный массив моделируемый вызов по ссылке начальное значение номер позиции нулевой символ /О нулевой элемент объявление массива одномерный массив определение пределов ошибка типа завышения (или занижения) на единицу передача массива функции передача по ссылке

Типичные ошибки программирования

4.1. Важно отметить различие между седьмым элементом массива и элементом массива семь . Поскольку индексы массива начинаются с О, седьмой элемент массива имеет индекс шесть, тогда как элемент массива семь имеет индекс 7 и ыа самом деле является восьмым элементом массива. Это - источник ошибок типа завышения (или занижения) на единицу.

4.2. Забывают присвоить начальные значения элементам массива, тре-буюш;им такого присваивания.

4.3. Задание в списке начальных значений большего числа значений, чем имеется элементов в массиве, является синтаксической ошибкой.

4.4. Присваивание значения именованной константе в выполняемом операторе является синтаксической ошибкой

4.5. Завершение директивы препроцессора #include точкой с запятой. Помните, что директивы препроцессора не являются операторами С++.

4.6. Ссылка на элемент, находящийся вне границ массива.

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

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

4.9. Неправильная ссылка на элемент двумерного массива а[х] [у] как а[х,у]. На самом деле, а[х,у] воспринимается как а[у], потому что С++ оценивает выражение (содержащее операцию последования - запятую) X , у просто как у (последнее из разделенных запятыми выражений).

Хороший стиль программирования

4.1. Старайтесь программировать понятно. Иногда имеет смысл пожертвовать более высокой эффективностью использования памяти или процессорного времени в пользу написания более понятной программы.

присваивание начальных значений спецификация типа const

массиву список начальных значений

проход пузырьковой сортировки строка

пузырьковая сортировка таблица значений

скаляр табулированный формат

сортировка трехмерный массив

сортировка массива элемент массива сортировка погружением

4.2. При использовании циклов с массивом индекс массива никогда не должен быть меньше нуля и должен всегда быть меньше, чем обш;ее количество элементов массива (меньше, чем размер массива). Удостоверьтесь, что условия завершения цикла предотвраш;ают обраш;е-ние к элементам, выходяш;им за пределы этого диапазона.

4.3. В программах должна быть обеспечена правильность всех вводимых значений, чтобы не допустить возможность влияния ошибочной информации на ход вычислений в программе.

4.4. Некоторые программисты, чтобы сделать программу понятнее, включают имена переменных в функции прототипов. Компиляторы игнорируют эти имена.

Советы по повышению эффективности

4.1. Иногда соображения эффективности далеко перевешивают соображения понятности.

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

4.3. Часто простейшие алгоритмы обеспечивают низкую производительность. Их достоинство лишь в том, что их легко писать, проверять и отлаживать. Однако, часто для получения максимальной производительности необходимы более сложные алгоритмы.

Замечания по мобильности

4.1. Эффекты (обычно серьезные) ссылок на элементы, выходяш;ие за границы массива, системно зависимы.

Замечания по технике программирования

4.1. Определение размера каждого массива с помощью именованной константы делает программу более масштабируемой.

4.2. Передавать массив по значению можно, используя простой прием, который мы объясним в главе 6.

4.3. Для предотвращения модификации исходного массива внутри тела функции можно в определении функции применять к параметру массив спецификатор типа const . Это еще один пример принципа наименьших привилегий. Функциям не должно быть позволено модифицировать массивы без крайней необходимости.

Упражнения для самопроверки

4.1. Заполнить пробелы в следующих утверждениях:

а) Списки и таблицы значений хранятся в .