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

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

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

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

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

Необходимо найти максимальный двузначный элемент в одномерном упорядоченном массиве кратный трем (делящийся на 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, 19:09   #2
Syuf
Форумчанин
 
Аватар для Syuf
 
Регистрация: 02.02.2010
Сообщений: 599
По умолчанию

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

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

Только не начинаются, а заканчиваются, как-то так:
Код:
// 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 вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


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


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS