Leetcode Array 中的 Binary Search II

有一类题，严格意义上讲不算Array中的二分法，但是他们确实用到了二分的思想，这里一并总结

1. Divide Two Integers.

说白了除法就是看被除数里有几个除数。挨个减是能想到的简单方法。 但是INT_MAX /1 会超时，比较笨。因此需要让除数指数增长，直到再增长就会超过被除数，然后剩下的部分继续这样做。注意越界的long long

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

int divide(int dividend, int divisor) { // Start typing your C/C++ solution below // DO NOT write int main() function int sign=1; if(dividend<0) sign=-sign; if(divisor<0) sign=-sign; long long a=abs((double) dividend); long long b=abs((double) divisor); long long ret=0; while(a>=b){ long long c=b; for(int i=0;a>=c;c=c<<1,i++){ a-=c; ret+=1<<i; } } re

2. Pow(x,n)
类似的 求n次方，递归求n/2次方然后相乘。注意当n为负数时，不可以直接将n取绝对值会越界,而是yy/x。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

double pow(double x, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if(n==0) return 1; if(n==1) return x; if(n%2==1){ double y=pow(x,n/2); return y*y*x; } if(n%2==0){ double y=pow(x,n/2); return y*y; } if(n%2==-1){ double y=pow(x,n/2); return y*y/x; } } };

3. sqrt(x)
也是二分，high=x,low=0. mid=(high+low)/2. 注意这里比较关键的是那些非整数结果的平方跟，他们返回的值y,一定是y*y<x; (y+1)*(y+1)>x. 因此high-low>1，这样才能保证最后一个loop的mid=low+1. 而low high也也在相应的条件下被赋予mid 而不是mid+-1最后返回low

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int sqrt(int x) { // Start typing your C/C++ solution below // DO NOT write int main() function long long high=x; long long low=0; if(x==0) return 0; if(x==1) return 1; while(high-low>1){ long long mid=(high+low)/2; if(mid*mid==x) return mid; else if(mid*mid>x) high=mid; else low=mid; } return low; }