# Java Solution Using Binary Search

• Worst case time complexity is O(nlgn) where n is the number of bits to represent dividend.

``````public int divide(final int dividend, final int divisor) {
long x = dividend, y = divisor;

boolean isPositive = !((x >= 0) ^ (y >= 0));  // equivalent to (x >= 0 && y >= 0) || (x < 0 && y < 0)

x = x < 0 ? -x : x;
y = y < 0 ? -y : y;

long result = 0;

while (x >= y) {
long power = findLargestPower(x, y);
result += (1L << power);
x -= (y << power);
}

result = isPositive ? result : -result;

return result >= Integer.MAX_VALUE || result < Integer.MIN_VALUE ? Integer.MAX_VALUE : (int) result;
}

private long findLargestPower(final long x, final long y) {
long left = 1, right = Integer.MAX_VALUE;
while (left <= right) {
long mid = left + (right - left)/2;
if ((y << mid) >= (y << (mid-1)) && (y << mid) <= x) {
left = mid+1;
} else {
right = mid-1;
}
}
return left-1;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.