Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Бишоп Д. -> "Эффективная робота Java 2" -> 233

Эффективная робота Java 2 - Бишоп Д.

Бишоп Д. Эффективная робота Java 2 — Спб.: Питер, 2002. — 592 c.
ISBN 966-552-107-1
Скачать (прямая ссылка): effektivnayarabotajava2002.djvu
Предыдущая << 1 .. 227 228 229 230 231 232 < 233 > 234 235 236 237 238 239 .. 259 >> Следующая

Алгоритм линейного поиска является примером цикла с двумя выходами (double-exit loop), т.е. цикл нормально завершится в обоих случаях: или значение будет найдено в последовательности, или конец последовательности будет достигнут раньше, чем будет найдено значение. Эти виды циклов подробно рассматривались в разделе 5.2, где последовательностью был поток вводимых данных, и повторно в разделе 8.3 при рассмотрении связных списков. Теперь воспользуемся этой логикой для выполнения поиска в массиве.
Преимущество поиска в массиве заключается в том* что мы знаем его длину. Следовательно, можно использовать цикл for наряду с возможностью контроля, которую этот цикл предоставляет (возможность завершения цикла, если значение не найдено). Вот первая попытка линейного поиска:
int і;
for ( і = 0; і< a.length; і++) if [а[і] = х) break;
Хотя этот цикл прост и аккуратен, он, к сожалению, имеет недостаток При его завершении мы не знаем, почему он закончился: потому чтп мм Т-ІЯ If Г пи тJWAifrte значение или потому что была просмотрена вся последовательность значений. Также
заметьте, что мы преднамеренно объявили і вне цикла, чтобы впоследствии можно
было получить а [ і ].
536
Глава 15. Структуры данных и алгоритмы
Это означает, что алгоритм возвращает два значения: индикатор да/нет (или булеву переменную) и индекс, что делает проблематичной возможность оформления поиска в метод, поскольку метод возвращает только одно значение (если не будет указан для возвращения объект, имеющий много значений)*
Можно применить следующую технологию (хотя мы не рекомендуем этого делать) — в случае, если поиск не увенчается успехом, назначить возвращаемому индексу значение, выходящее за диапазон массива- Такими значениями могут быть или — I, или длина массива. Лучший способ решения этой проблемы—использование определенных пользователем исключений. Рассмотрим следующий вариант:
class ItemNotFoundException extends Exception ( } item а П ” new a[n];
static int LinearSearch (item a [], item x) throws ItemNotFoundException { for tint і *¦ 0; i< a-length; i++)
If fx.equals(a[I])} return i;
// Искомое значение не найдено: кет нормального возврата, threw ItemNotFoundException(J;
1
// Проверка метода, try f
int found = XiinearSearch (a, x);
// Все необходимые операторы для работы с объектом a[found].
ш б ¦
}
catch (ItemNotFoundException е) {
// реагирование ка отсутствие "х" в массиве
г в В-
}
Методу передается массив и элемент (объект), который нужно найти. Метод просматривает массив и сравнивает каждый элемент с х, ислользуя длину массива как условие для остановки цикла (что делает метод применимым для массивов любой длины). Сравнение производится посредством вызова метода equals, поскольку здесь мы принимаем, что элементы являются объектами. Если элемент найден, то цикл возвращает объект немедленно, если же цикл безрезультатно проходит весь массив, то мы “выбрасываем” объект-исключение.
Вызывающий метод имеет пару t ry-catch. Если поиск увенчался успехом, выполняется следующий оператор, каким бы он ни был. Если нет, управление передается обработчику, определенному в блоке catch, и выполняются альтернативные действия. На Web-узле есть тестовая программа, которая демонстрирует этот метод.
Двоичный поиск
Если данные, просматриваемые в процессе поиска, упорядочены (отсортированы), то можно применить более эффективные методы, чем линейный поиск. Одним из таких методов является двоичный поиск (binary search). Он предусматривает разделение последовательности пополам и выполнение поиска только в той части, в которой должно находиться искомое значение. Поскольку принимается, что последовательность отсортирована, то можно уверенно определить, в какой части находится искомое значение.
Линейный и двоичный поиск
537
Например, у нас есть отсортированная последовательность
23 45 61 65 67 70 82 89 90 99
и мы ищем значение 90, Можно разделить последовательность пополам (между 67 и 70) и увидеть, что 90 должно находиться в правой части:
70 82 89 90 99
Эту подпоследовательность делим еще на две части (между 89 и 90) и вновь переходим в правую часть:
9Q 99
В этой последовательности находится только два элемента, но мы вновь ее делим и перемещаемся влево, где находим 90.
Этот процесс включает в себя три разделения и три сравнения, что гораздо удобнее, чем девять сравнений при линейном поиске.
Очевидно, что двоичный поиск работает быстрее, чем средний алгоритм поиска, но так бывает не всегда. Если бы числом, которое нужно найти, было 23 (в нашем примере оно стоит в последовательности первым)* двоичный поиск все равно стартовал бы с середины последовательности и постепенно продвигался бы влево к этому числу. Лучший способ сформулировать такой двоичный поиск — использовать технологию, которая называется рекурсией.
Рекурсия позволяет нам описать операцию, исходя из ее же принципов работы, базируясь на модифицированных данных и включая условия для завершения.
Предыдущая << 1 .. 227 228 229 230 231 232 < 233 > 234 235 236 237 238 239 .. 259 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.