给别人做网站多少钱,佳天下装饰公司怎么样,中国人事建设部网站,wordpress回收站位置一、二分查找概念 二分查找也叫折半查找#xff0c;是在一组有序(升序/降序)的数据中查找一个元素#xff0c;它是一种效率较高的查找方。
二、二分查找原理 1.二分查找的数组必须是有序数值型数组。 2.将想要查找的目标元素与查找范围内的中间元素进行比较#xff0c;如果…一、二分查找概念 二分查找也叫折半查找是在一组有序(升序/降序)的数据中查找一个元素它是一种效率较高的查找方。
二、二分查找原理 1.二分查找的数组必须是有序数值型数组。 2.将想要查找的目标元素与查找范围内的中间元素进行比较如果相等查找结束反之把目标元素分到较大或者是较小的范围在进行比较。 3.通过分组可将查找范围缩小一半。 4.重复步骤二直到目标元素与查找范围内中间元素相等或者没有这个目标元素查找结束。 5.二分查找的时间复杂度O(log2n) 三、二分查找的具体步骤
前提给定一个内含n个元素的有序数组A满足A0A1A2·······An-1,一个待查值target 如果找到返回索引 如果找不到返回索引-1 1、设置i0,jn-1 2、如果ij,结束查找没有找到返回-1 3、设置m为中间索引则mfloor((ij)/2), floor是向下取整ij/2 的最小整数) 4、如果 targetAm ,设置jm-1, 跳到第2步 5、如果 Am target,设置im1, 跳到第2步 6、如果 Am target,结束查找找到了 四、图示所示-基础版
查找target4 编码
/*** 二分查找基础版** param arr 查找升序数组* param target 目标值* return 找到返回索引* 找不到返回-1*/public static int binarSearchBasic(int[] arr, int target) {//设置初值的索引int i 0;int j arr.length - 1;//循环while(ij){ //在范围内int mid(ij)/2;//获取中间值if(targetarr[mid]){ //目标左边jmid-1;}else if(arr[mid]target){//目标右边imid1;}else { //找到了return mid;}}return -1;} 五、图示所示-改进版 问题对应ij)/2 有没有问题 如果超过正整数最大值表示的范围由正变负发生错误 Testpublic void main() {int i 0;int j Integer.MAX_VALUE - 1;int m (i j) / 2;System.out.println(m); //1073741823//如果目标在右侧i m 1;System.out.println(i); //1073741824System.out.println(j); //2147483646System.out.println(ij); // -1073741826
// m (i j) / 2;m (i j) 1; //1610612735System.out.println(m); //-536870913//此时发生错误超过正整数能表示的范围由正变负。//二进制数//把java二进制数最高位为符号位代表: -1073741826//不把二进制数最高位为符号位代表3221225470} 修改无符号右移1位 1 (可以使更多的语言) m (i j) 1 查找target13 编码
/*** 二分查找改动版** param arr 查找升序数组* param target 目标值* return 找到返回索引* 找不到返回-1*/public static int binarSearchUpdate(int[] arr, int target) {//设置初值的索引int i 0;int j arr.length ; //第1处//循环while(ij){ //第2处//中间值int mid(ij)1;//获取中间值if(targetarr[mid]){ //目标左边jmid; //第3处}else if(arr[mid]target){//目标右边imid1;}else { //找到了return mid;}}return -1;}
