5-29.两数相除

题目描述：

解题思路：

与其说是二分查找，倒不如说是递归。第一遍并不知道如何下手，看了题解之后。有那么一点明白了。

假如是计算11除以3的值。

• 首先11>3，我们可以知道最终的结果res至少是1；
• 然后让3翻倍，变成6，此时6<11；因此res也翻倍，此时结果至少是2；
• 再让6翻倍，变成12，此时12>11；而res翻倍之后是4；也就是说最终的答案在2-4之间。
• 至于比2大多少，就让11减去最后一次比他小的那个数，即11-6=5；计算5除以3的值，即是比2大的值；这里递归就出现了。

代码：

class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 1){return dividend;}
        //如果是最小的整数除以-1，此时要返回最大的整数，不然会溢出
        if(dividend==Integer.MIN_VALUE && divisor==-1){return Integer.MAX_VALUE;}
        if(divisor == -1){return -dividend;}
        if(dividend == 0 ){return 0;};
        long a = dividend;
        long b = divisor;
        int sign = 1;
        if((a > 0 && b > 0) || (a < 0 && b < 0)){
            sign = 1;
        }else{
            sign = -1;
        }
        a = (a > 0) ? a : -a;
        b = (b > 0) ? b : -b;
        int res = div(a,b);
        if(sign > 0){
            return res;
        }
        return 0 - res;
    }
    int div(long a,long b){
        if(a < b){return 0;}
        long min = 1;//记录当前最小的解
        long testB = b;//最小解对应的测试值
        while((testB << 1) < a){
            min = min << 1;//最小解翻倍
            testB = testB << 1;//测试值翻倍
        }
        return (int)(min + div(a - testB,b));
    }
}

5-29.两数相除

原文：https://www.cnblogs.com/forrestyu/p/14651270.html