Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

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

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

это мысль! А как бинарным найти элемент, с которого начинаются двузначные? Какое должно быть условие?
Vellosity вне форума Ответить с цитированием
Старый 02.06.2011, 21: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 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск минимального элемента в перевернутом массиве 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 19:47
Написать подпрограмму-процедуру поиска максимального элемента в массиве Noxil Паскаль, Turbo Pascal, PascalABC.NET 3 27.11.2008 21:39