Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Двоичный поиск - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Класс «Здание» с данными количество этажей, подъездов и квартир http://www.cyberforum.ru/cpp-beginners/thread271648.html
1. Объявить класс по приведенному ниже заданию в соответствии с номером варианта и определить для него конструктор по умолчанию, конструктор инициализации и конструктор преобразования. 2. Определить...
C++ Триугольник Треугольник ABC заданы координатами своих вершин на плоскости. Найти внутренние углы треугольника (в радианах). http://www.cyberforum.ru/cpp-beginners/thread271646.html
Функции C++
Треугольник ABC заданы координатами своих вершин на плоскости. Найти внутренние углы треугольника (в радианах).
C++ Сформировать другой массив, в который поместить сначала числа меньшие среднего арифметического значения этого массива, затем – большие.
Дан целочисленный массив, состоящий из 15 элементов. Сформировать другой массив, в который поместить сначала числа меньшие среднего арифметического значения этого массива, затем – большие.
C++ ярлык http://www.cyberforum.ru/cpp-beginners/thread271636.html
Здравствуйте господа програмисты!Возникла проблема-как програмно создать ярлык на свою программу на рабочий стол? Заранее всем огромное спасибо!!! Добавлено через 5 минут на dev c++ консольное...
C++ Как созадть такой экземпляр? Пусть есть класс: class A { protected: type field; .... }; а выше описан тип (возможно класс, или структура) type, или макрос type - синоним существующего (возможно стандартного) типа. В... подробнее

Показать сообщение отдельно
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:04
Цитата Сообщение от taras atavin Посмотреть сообщение
Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.
Либо мы не понимаем друг друга, либо Вы не понимаете сути бинарного поиска. Если массив отсортирован, то для поиска элемента "отступать" необходимо ровно на половину текущего интервала поиска. В итоге сложность получится в лучшем случае O(logn). В худшем случае O(n). Это касается и двоичных деревьев поиска тоже. Именно двоичных, к которым не применяются алгоритмы балансировки. Видели когда-нибудь такое дерево?
Название: binary_tree.png
Просмотров: 98

Размер: 7.3 Кб
Сколько потребуется итераций, чтобы найти лист дерева? Правильно - O(n). Судя по Вашей логике, здесь тоже будет последовательный поиск. В бинарных деревьях поиска сложность абсолютно такая же: O(logn) - в лучшем случае и O(n) - в худшем.

Если речь идет о касательно конкретно этой задачи, то я и не говорил, что бинарный поиск (или метод деления пополам) здесь должен быть, я говорил, что задание "бредовое". То есть в этой задаче никакого бинарного поиска и не будет - будет просто отсортированный массив. Здесь как такового поиска не будет вообще
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru