笔记

二分查找 BinarySearch

public static int indexOf(int key, int[] a) {        int lo = 0;        int hi = a.length - 1; // 记住要-1        int mid;        while (lo <= hi) { //记住有等号            mid = (lo + hi) / 2;            if (key < a[mid])                hi = mid - 1;            else if (key > a[mid])                lo = mid + 1;            else                return mid;        }        return -1;    }

练习题

求对数

Exe 1.1.14

编写一个静态方法 lg()，接受一个整型参数N，返回不大于log2(N)的最大整数。不要使用Math库。

public static int lg(int N){            // m = log a N             int a=2; //a为底数                        int m=0;             for(;N>1;N/=a){                 m++;            }            return m;        }

递归乘法/乘方

Exe 1.1.18

乘法

函数即为乘法的递归形式，返回值为a*b

分析：

引入二进制例子

2|4……0

2|2……0

2|1……1

4的二进制表示为100

eg:3*4

011

* 100

11000

将b看做二进制，当b的二进制位为1时，与a相乘。由1的位置决定a乘以几，依次为1，2，4，8，16，...,2^n。将各个乘积累加起来。

（类似于十进制的乘法运算方式，不同位置的乘法依次会乘以1，10，100，1000，...，10^n，最后累加）

代码思想：

1.循环判断

大循环

判断b的二进制位是否为1{若是，sum+=a;若不是，不需要做任何操作，因为加0不影响}

a=a*2

继续看更高一位，直到看完。

return sum。

（类似于综合法）

public static int multi(int a, int b) {        int isys = 4; //n进制        int sum=0; //这个不能写在for里面，因为for里面声明的为局部变量。        for (; b != 0; b /= isys) {            if (b % isys != 0) {                sum += a * (b % isys);            }            a *= isys;        }        return sum;    }

2.递归算法

递归算法就是return 本次结果+用另外的参数调用自己。

（类似于分析法，抽丝剥茧回去）

public static int multi2(int a, int b)    {        if (b == 0) return 0;        if (b % 2 == 0) return multi(2*a, b/2);        return multi(2*a, b/2) + a;    }

乘方的递归形式

public static int power(int a, int b)    {        if (b == 0) return 1;        if (b % 2 == 0) return power(a*a, b/2);        return power(a*a, b/2) * a;    }

交换

用异或的方式交换两个变量，不使用第三个变量，节省一个空间。

然而这个函数方法本身并没有用，因为方法中若传递参数为基本型（如int），在方法中对其值的改变并不会在主函数中产生影响。

public static void exch(int a, int b){        a=a^b;        b=a^b;        a=a^b;    }

待补充

局部变量；全局变量；静态变量

转载地址：http://awwzx.baihongyu.com/

你可能感兴趣的文章