Разделите два числа с помощью двоичного поиска без использования оператора / и %
Учитывая два целых числа, одно является делимым , а другое — делителем , нам нужно найти частное при делении делимого на делитель без использования каких-либо операторов «/» и «%» .
Примеры:
Input: dividend = 10, divisor = 2
Output: 5
Explanation: 10/2 = 5.Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333… which is truncated to 3.Input: dividend = 10, divisor = -2
Output: -5
Explanation: 10/-2 = -5.
Подход: решить проблему с помощью бинарного поиска следуйте следующей идее:
We already know that Quotient * Divisor ≤ Dividend and the Quotient lie between 0 and Dividend. Therefore, we can assume the Quotient as mid, the Dividend as higher bound and 0 as the lower bound and can easily use binary search to satisfy the terms of division which is Quotient * Divisor ≤ Dividend.
Следуйте инструкциям, чтобы решить проблему:
- Сначала установите high = дивиденд и low = 0 .
- Затем нам нужно найти середину (т.е. частное) = минимум + (максимум – минимум) / 2 .
- Затем мы выполняем бинарный поиск в диапазоне от 0 до делимого.
- Если средний * делитель > делимое , то обновить высокий = средний – 1 .
- В противном случае мы обновляем low = mid + 1
- Значение середины, которое удовлетворяет условию (т. е. середина * делитель ≤ делимого), является нашим Частным.
- Затем мы возвращаем его, проверяя четность.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(log N), так как используется алгоритм бинарного поиска.
Вспомогательное пространство: O(1), так как дополнительное пространство не использовалось.