Высота наибольшего треугольника, который можно вписать в прямоугольник

Дан прямоугольник длины L и ширины B. Задача состоит в том, чтобы вывести максимально возможную целочисленную высоту наибольшего треугольника, который может быть вписан в него, так, чтобы высота треугольника была равна половине основания.

Примеры:

Input: L = 3, B = 4
Output: 2

Input: L = 8, B = 9
Output: 4

Input: L = 325, B = 300
Output: 162

Наивный подход: самый простой подход состоит в том, чтобы перебрать диапазон [0, min(L, B)] в обратном порядке, и если текущее значение меньше или равно max(L, B) / 2 , затем напечатать текущее значение как ответ и разорвать петлю.

Временная сложность: O(мин(L, B))
Вспомогательное пространство: O(1)

Подход бинарного поиска: описанный выше подход можно оптимизировать, используя технику бинарного поиска и учитывая тот факт, что всегда оптимально выбирать основание треугольника на стороне с максимальной длиной стороны прямоугольника. Выполните следующие шаги, чтобы решить проблему:

• Если L больше, чем B , поменяйте местами значения.
• Инициализируйте три переменные, скажем, младше 0 и старше L , чтобы выполнить бинарный поиск в диапазоне [0, L].
• Кроме того, инициализируйте переменную, скажем, res как 0 , чтобы сохранить максимально возможную длину высоты.
• Итерируйте, пока низкий уровень меньше или равен высокому , и выполните следующие шаги:
  • Инициализируйте переменную, скажем, mid , и установите для нее значение low + (high — low) / 2 .
  • Если значение mid ≤ B/2 , то назначьте mid на res , а mid +1 на low .
  • В противном случае установите от высокого до среднего – 1 .
• Наконец, после выполнения вышеуказанных шагов выведите полученное значение в res .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log (мин (L, B)))
Вспомогательное пространство: O(1)

Эффективный подход: описанный выше подход можно дополнительно оптимизировать, заметив, что при размещении основания треугольника на стороне длины max(L, B ) максимальная высота будет равна min(max(L, B)/ 2, мин(L, B)) . Выполните следующие шаги, чтобы решить проблему:

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)