IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> поиск элемента в массив
сообщение
Сообщение #1


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Добрый день!
Есть следующие задание
В программе бинарного поиска внутри цикла осуществляются две проверки, хотя могла быть только одна (при увеличении числа проверок вне цикла). Напишите программу, предусмотрев в ней одну проверку внутри цикла. Оцените разницу во времени выполнения.
/* binsearch: найти x в v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n-1;
while (low <=high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid+1;
else /* совпадение найдено */
return mid;
}
return -1; /* совпадения нет */
}
ничего кроме
int binsearch2(int x, int v[], int n)
{
int i;
for(i=0; i<n; ++i) if (v[i]=x) return i;
return -1;
}
в голову не идет...
а как правильно?
заранее благодарен.



--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






K&R мучаешь? smile.gif А есть ли смысл тогда просить подсказку?

Добавлено через 9 мин.
Если все-таки хочешь посмотреть на цикл с одним сравнением - то:

Спойлер (Показать/Скрыть)


Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата(volvo @ 1.01.2008 22:19) *
K&R мучаешь? smile.gif А есть ли смысл тогда просить подсказку?
думаешь не стоит... ладно, подумаю еще сам...


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


вот что я еще придумал...
int binsearch4(int x, int v[], int n){
int low = 0;
int high = n-1;
int mid=((low + high) / 2);
while ((x!=v[mid]) && (low!=high)){
if (x < v[mid])
high = mid - 1;
else
low = mid+1;
mid = (low + high) / 2;
}
if (x==v[mid]) return mid; /*else*/
return -1;
}
тут, правда, в условии цикла дабавленно условие... сейчас посмотрю твой код...

upd
volvo, не мог бы ты снабдить свой код комментариями(особенно часть после цикла), а зоодно оценить мой код...

Сообщение отредактировано: compiler -


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.09.2020 20:16
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name