Бинарный поиск первого элемента, удовлетворяющего условию

@Vtulhu · Регистрация: 12.08.2011

Студворк — интернет-сервис помощи студентам

Допустим, есть числовой массив, все элементы которого заранее упорядочены по возрастанию. Нужно найти первый (от начала массива) элемент, который не меньше заданного числа. Коллизию вида "а что, если такого элемента не найдётся?" обрабатывать не нужно. Проще добавить к массиву ещё одну ячейку, содержащую условную бесконечность.

Пытался написать сам, тем более что я знаю метод бинарного поиска и уже делал такую прожку, но для случая, когда искомое число гарантированно присутствует в массиве. Казалось бы, микроскопическое изменение - вместо равенства надо проверять на больше или равно. Ан нет! В любом случае - зачем изобретать велосипед? Наверняка где-то есть...

@Igor3D · 15.02.2013, 18:46

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int UpperLimit( const int * a, int count, int bound )
{
 int beg = 0, end = count - 1;
 if (a[beg] >= val) return 0;
 if (a[end] < val) return -1;  // not found
 while (end - beg > 1) {
  int mid = (beg + end) / 2;
  if (a[mid] < val)
   beg = mid;
  else 
   end = val;
 }
 return end;
}

Сообщение от Vtulhu

В любом случае - зачем изобретать велосипед? Наверняка где-то есть...

Ну как Вам сказать... Такие соображения кажутся "практичными", а кому-то может и "мудрыми". Однако чем больше Вы "списываете" (как это называлось в советской школе) - тем меньше у Вас остается своих мыслей и мозгов. Выводы делайте сами

@Vtulhu · 15.02.2013, 20:07 **[ТС]**

Сообщение от Igor3D

Ну как Вам сказать... Такие соображения кажутся "практичными", а кому-то может и "мудрыми". Однако чем больше Вы "списываете" (как это называлось в советской школе) - тем меньше у Вас остается своих мыслей и мозгов. Выводы делайте сами

Когда есть время - я предпочитаю всё делать сам. Хотя бы потому что это интересно. Но эта штуковина нужна срочно.

Спасибо!

Новые блоги и статьи Все статьи Все блоги /
Вот уже год прошел, как у меня домен в reg.ru ... Etyuhibosecyu 16.04.2026 И ничего они мне не сделали. Если отвязать карту, никакие услуги они не навяжут. Я бы с радостью продлил еще на два года, чтобы не мучиться с временным доменом и меня уже знали по red-star-soft. com,. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .

@Vtulhu 431 / 385 / 200 Регистрация: 12.08.2011 Сообщений: 1,610

	Бинарный поиск первого элемента, удовлетворяющего условию 15.02.2013, 16:19. Показов 1264. Ответов 2 Метки нет (Все метки) Допустим, есть числовой массив, все элементы которого заранее упорядочены по возрастанию. Нужно найти первый (от начала массива) элемент, который не меньше заданного числа. Коллизию вида "а что, если такого элемента не найдётся?" обрабатывать не нужно. Проще добавить к массиву ещё одну ячейку, содержащую условную бесконечность. Пытался написать сам, тем более что я знаю метод бинарного поиска и уже делал такую прожку, но для случая, когда искомое число гарантированно присутствует в массиве. Казалось бы, микроскопическое изменение - вместо равенства надо проверять на больше или равно. Ан нет! В любом случае - зачем изобретать велосипед? Наверняка где-то есть... 0