Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 02.06.2011, 19:27   #1
Vellosity
 
Регистрация: 17.04.2011
Сообщений: 9
Репутация: 10
Восклицание Поиск элемента в массиве методом бинарного поиска

Необходимо найти максимальный двузначный элемент в одномерном упорядоченном массиве кратный трем (делящийся на 3 без остатка). Например массив 1, 5, 8, 9, 10, 16, 18, 21. То есть нужно вывести 21. Поиск надо провести БИНАРНЫМ поиском. Вот бинарный поиск(постепенное деление отрезка поиска пополам) - я написал. Но я написал для определенного поиска элемента в соответствии с ключом поиска. А так чтобы сделать нахождение не ключа, а максимального элемента - смекалки не хватает. Пожалуйста помогите!
Код:
a=0;
b=N-1;
mid=0;
while (mas[mid]!=key)
{
	mid=(a+b)/2;
	if (mas[mid]==key)
	{
		printf ("Elem found");
		return mid;
	}
	if (a==b)
	{
		printf ("Not found");
	}
	if (mas[mid]>key)
	{
		b=mid-1;
	}
	if (mas[mid]<key)
	{
		a=mid+1;
	}
}
Vellosity вне форума   Ответить с цитированием
Старый 02.06.2011, 20:09   #2
Syuf
Участник клуба
 
Аватар для Syuf
 
Регистрация: 02.02.2010
Адрес: В Visual Studio 2008
Сообщений: 599
Репутация: 70
По умолчанию

Не получится. Это не монотонная функция (кратность трем с возрастанием никак не связана). Единственное, что можно, это найти, где начинаются двузначные элементы - бинпоиском, а потом линейным с конца найти максимальный и кратный трем.
__________________
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
Syuf вне форума   Ответить с цитированием
Старый 02.06.2011, 20:34   #3
Vellosity
 
Регистрация: 17.04.2011
Сообщений: 9
Репутация: 10
По умолчанию

это мысль! А как бинарным найти элемент, с которого начинаются двузначные? Какое должно быть условие?
Vellosity вне форума   Ответить с цитированием
Старый 02.06.2011, 21:56   #4
Syuf
Участник клуба
 
Аватар для Syuf
 
Регистрация: 02.02.2010
Адрес: В Visual Studio 2008
Сообщений: 599
Репутация: 70
По умолчанию

Только не начинаются, а заканчиваются, как-то так:
Код:
// Function returns the last two-digit number

int size = sizeof data / sizeof data[0];
if(data[size - 1] < 100)
   return size - 1;
int left = 0, right = size - 1, middle;
while(left < right)
{
   middle = (left + right)/2;
   if(data[middle] >= 100)
      right = middle;
   else
      left = middle + 1;
}
return (middle ? middle - 1 : 0);
__________________
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
Syuf вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск минимального элемента в перевернутом массиве Kovax Паскаль 11 27.02.2011 15:38
Поиск элемента в двухмерном массиве (Assembler 86) bookkc Помощь студентам 1 26.11.2010 19:14
Поиск максимального отрицательного элемента в массиве Tomoa Microsoft Office Excel 6 27.11.2009 16:10
Поиск максимального элемента в массиве Alexus999 Помощь студентам 8 08.06.2009 19:47
Написать подпрограмму-процедуру поиска максимального элемента в массиве Noxil Паскаль 3 27.11.2008 22:39


14:13.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.