郑州大学科技园手机网站建设,wordpress 新手指南,游戏交易类网站seo怎么做,wordpress注册链接目录 1. 二分查找2. 补充#xff1a;二进制运算2.1 十进制与二进制的相互转换2.1.1 十进制转二进制2.1.2 二进制转十进制 2.2 机器数 真值2.3 原码 补码 反码2.4 二进制的加减乘除2.5 移位运算 1. 二分查找
思想#xff1a; 有序数组#xff0c;从中找值
实现#xff1a;… 目录 1. 二分查找2. 补充二进制运算2.1 十进制与二进制的相互转换2.1.1 十进制转二进制2.1.2 二进制转十进制 2.2 机器数 真值2.3 原码 补码 反码2.4 二进制的加减乘除2.5 移位运算 1. 二分查找
思想 有序数组从中找值
实现 while 循环时间复杂度log(n) public static int binarySearch01(int[] arr, int target) {int i 0;int j arr.length - 1;// 是因为目标值可能在 0 或 arr.length - 1 索引处while (i j) {// 用移位运算防止溢出int mid (i j) 1;if ( target arr[mid]) {j mid - 1;} else if (arr[mid] target){i mid 1;} else {return mid;}}return -1;}优化把 j 只作为一个右边界不能指向目标值 public static int binarySearch02(int[] arr, int target) {int i 0;int j arr.length;// 这里如果使用 i j会导致查找不存在的元素的时候出现死循环while (i j) {int mid (i j) 1;if (arr[mid] target) {j mid;} else if (arr[mid] target){i mid 1;} else {return mid;}}return -1;}分析 往左查找的消耗是往右查找消耗的 1/2不均衡。因为往右查找需要比较两次 if 优化平均两侧查找消耗 public static int binarySearch04(int[] arr, int target) {int i 0;int j arr.length;while (1 j - i) {int mid (i j) 1;if (target arr[mid]) {j mid;} else {// 这里不能 1了如果目标值就在中间就找不到了i mid;}}if (arr[i] target) {return i;}return -1;}利用 api 写个二分查找找到目标值就返回索引 数组找不到就插入再返回 public static MapInteger, int[] binarySearch05(int[] arr, int target) {int i Arrays.binarySearch(arr, target);MapInteger, int[] res new HashMap();if (0 i) {res.put(i, arr);return res;}int targetIndex abs(i 1);int[] arr0 new int[arr.length 1];System.arraycopy(arr, 0, arr0, 0, targetIndex);arr0[targetIndex] target;System.arraycopy(arr, targetIndex, arr0, targetIndex 1, arr.length - targetIndex);res.put(targetIndex, arr0);return res;}Arrays.binarySearch 包含多种类型的数据这里看 int 的 binarySearch0 的返回值 - 插入点 - 1 为什么不直接返回 -插入点答为了防止插入点为0出现歧义 public static int binarySearch(int[] a, int key) {return binarySearch0(a, 0, a.length, key);}private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {int low fromIndex;int high toIndex - 1;while (low high) {int mid (low high) 1;int midVal a[mid];if (midVal key)low mid 1;else if (midVal key)high mid - 1;elsereturn mid; // key found}return -(low 1); // key not found.}二分查找返回最左/最右的索引相同元素情况 /*** Desc falg -1 返回最左索引flag 1 返回最右索引*/public static int binarySearchLeftOrRight(int[] arr, int target, int flag) {int i 0;int j arr.length - 1;int index -1;while (i j) {int mid (i j) 1;if (target arr[mid]) {j mid - 1;} else if (arr[mid] target) {i mid 1;} else {index mid;if (1 flag) {i mid 1;} else {j mid - 1;}}}return index;}优化 二分查找返回最左/最右的索引相同元素情况 /*** param flag -1 返回最左索引 1 返回最右索引* return int 存在返回对应索引不存在返回 - 插入点 - 1*/public static int binarySearchLeftOrRight(int[] arr, int target, int flag) {int i 0;int j arr.length - 1;while (i j) {int mid (i j) 1;if (flag 1 ? target arr[mid] : target arr[mid]) {j mid - 1;} else {i mid 1;}}int index flag 1 ? i - 1 : i;if (target arr[index]) {return index;} return - index - 1;}2. 补充二进制运算
2.1 十进制与二进制的相互转换
2.1.1 十进制转二进制
方法短除法 整数 逆序排列 小数 顺序排列 原则 一直转换到小数部分清零为止 思考 有些小数部分是无法清零的该怎么处理 这时候就要引入误差/精度了比如说0.33转换成二进制误差小于1‰那么我假设转换后的结果为 x那么要求就是 |x - 0.33| 1‰即 0.319 x 0.331。 那么如何快速计算出结果呢 进制转换工具 所以 x 取 0.0101010001 就OK了 验证一下 没问题。 2.1.2 二进制转十进制
整数10101101 → 173 向右减权1*2^7 0*2^6 1*2^5 0*2^4 1*2^3 1*2^2 0*2^1 1*2^0小数0.1101 → 0.8125 向右减权1*2^-1 1*2^-2 0*2^-3 12^-42.2 机器数 真值
机器数 数字在计算机中的二进制表示形式。在计算机中数字以二进制形式存储和处理。机器数的最高位是符号位用于表示数字的正负。正数的符号位为0负数的符号位为1。机器数的大小受到计算机字长的限制字长决定了机器数的表示范围。
// 不同位的计算机中表示 5
00000101 # 8位
00000000 00000000 00000000 00000101 # 32位
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000101 # 64位64位计算机能一次读8byte32位能一次读 4byte可通过 cmd 输入 systeminfo 查看计算机参数 比如某机器的机器数大小是 2 byte那么它存储数字 5 的机器数就是0000 0101最左边的 0 表示正数其表示 -5 的机器数就是 1000 0101 真值 带符号位的机器数对应的真正数值可以通过将机器数转换为十进制数来获得。 比如机器数 1000 0101 的真值是 -50000 0101 的真值是 5。 2.3 原码 补码 反码
原码 最高位表示符号位其余位表示数值的绝对值和机器数一个意思。
反码 正数的反码和原码相同负数的反码是在其原码的基础上符号位不变其余各位取反。 比如正数5的反码和原码都是00000101负数-5的反码是11111010 。 补码 正数的补码和原码相同负数的补码是在其反码的基础上加1。 比如正数5的补码和原码都是00000101负数-5的补码是11111011。 小结一下对于正数原码 反码 补码对于负数反码 原码标志位不变其余取反1变成00变成1补码 反码 1。
补充负数的补码转原码
先取反然后 1
2.4 二进制的加减乘除
加法 正数 负数 我们放到减法里面说
方法从右往左加逢二进一
减法
方法都换成补码然后相加相加的结果就是答案 因为我们是在 8 位二进制里面做加减所以超出溢出的 1 要舍去
乘法
正数与十进制一样按位相乘然后相加负数摘掉标志位然后相乘最后根据两个符号位来判断正负
除法
正数正数与十进制一样按位相除如果被除数的最高位小于除数的最高位则除法运算结束。被除数的剩余位数即为余数负数负数取补码然后相除 注意进制负数除法的结果可能是有限的也可能是无限循环的。在实际计算中可能需要根据具体情况进行舍入或截断
2.5 移位运算
二进制移位运算 左移将一个数的二进制表示向左移动指定的位数右侧用0填充 可以把 看做是 *2 操作 右移将一个数的二进制表示向右移动指定的位数正数高位用0填充负数高位用1填充 可以把 看做是 /2 操作一直右移正数会变成 0负数会变成 -1为了保证它是负数所以会补个 1 无符号右移位不管正数还是负数高位都用0补齐 注意事项1 在做移位运算的时候要考虑当前类型的大小如下 声明一个 int 整型 -11、11
-11int 2 : 原二进制:11111111111111111111111111110101二进制: 111111111111111111111111111101十进制: 107374182111int 31 : 原二进制: 1011二进制: 10000000000000000000000000000000十进制: -2147483648
11int 32 : 原二进制: 1011二进制: 1011十进制: 11注意事项2 Java 中会将最高位看做符号位所以当数值 2^31 的时候最高位会被当做符号位 1从而编程负数。 public static void main(String[] args) {int i (int) pow(2, 31);int j 1;System.out.println(i);System.out.println(Integer.toBinaryString(i));System.out.println(i j);System.out.println(Integer.toBinaryString(i j));System.out.println( (i j) / 2 );System.out.println( (i j) 1);}
