二分查找--折半查找--看完这篇学不会你来打我

二分查找前言二分查找(binary search)也叫折半查找是一种在有序数组中基于分治策略的高效搜索算法因为它的有序性使得我们可以用“减而治之”的策略来进行查找。本文将大家讲一下二分查找的原理和代码1为什么要用二分查找1.1顺序查找暴力搜索最简单的查找也就是顺序查找只需要在数组中逐一的将target从前往后判断直到找到相等元素这个想必都很容易想到。在无序数组中查找指定元素target时由于没有更多的信息所以在最坏的情况下比如数组中不含target——只有依次遍历到最后一个元素后才可以得到结论。时间复杂度此时是o(n)。如果是无序数组这样做似乎无可厚非如果是有序数组这样做似乎就太过于老实了那么就有人要问了主播主播有没有查找效率更高的方法有的兄弟有的——二分查找intsearch(int*nums,intnumsSize,inttarget){for(inti0;inumsSize;i){if(nums[i]target){//找到了returni;}}return-1;//没找到没有走到if心里}intsearch(vectorintnums,inttarget){for(inti0;inums.size();i){if(nums[i]target){returni;}}return-1;}1.1.2 时间复杂度在有序数组中查找方法时间复杂度顺序查找o(n)二分查找o(logn)二分查找由于用到了数组的有序性大大提高了算法效率1.2 二分查找的原理及代码1.2.1二分查找原理其实大多数人应该很容易想明白举个例子要在这个{2,4,5,7,8,9,12}里面用二分查找元素8我采用左右都是闭区间这种方式仔细说一下[left,right]这种写法左右都是闭区间[left,right]while (left right) 这里用 因为left right是有意义的所以用 或者想一下如果换了上面这个例子如果到最后8了left right退出循环返回-1这不坏了吗if (nums[mid] target)里面 right 要赋值为 mid - 1因为现在这个nums[mid]一定不是target那接下来要查找的左区间最后的位置就是 mid - 1nums[mid] target的情况是一个道理要选mid1intbinsearch(int*nums,intnumsSize,inttarget){intleft0;intrightnumsSize-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){rightmid-1;}elseif(nums[mid]target){leftmid1;}else{returnmid;}}return-1;}intbinsearch(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmidleft(right-left)/2;//这里这样写是防止它越界if(nums[mid]target){rightmid-1;}elseif(nums[mid]target){leftmid1;}else{returnmid;}}return-1;}时间复杂度 o(n)空间复杂度 o(1)大多数初学者或许有疑问这里为什么要这么写int mid left (right - left) / 2;而不是int mid (right left) / 2;其实为了防止leftright这个加起来的结果int越界为了避免越界我们通常采用left (right - left) / 2;另一种开区间的写法我放在最后1.2.2 最坏情况逐行分析一下代码很容易发现如果我们先判断的是nums[mid] target也就是成功判定的话接下来我们要往左半部分如果失败呢我们还要继续判断nums[mid] target从而判断它能否往右这样看往左需要一次判断而往右一共需要两次判断这样就造成了不同情况所对应的查找长度的不均衡一直往左和一直往右查找长度相差约两倍即使目前来看它在最坏的情况下也可以保证O(log n),但是经过我们仔细观察一下还略有不足那么就有人要问了主播主播这样的二分查找的确很强但是还是不够平衡稳定而且还是太长了那么有没有又简单好理解又平衡的二分查找呢有的兄弟有的——二分查找pro版1.3 二分查找 pro和promax上面这种二分查找在时间复杂度上看的确可以了还是略有瑕疵白圭之玷尚可磨也之所以在它的平衡上出现问题最根本的问题是往左边的一次判断和往右边的两次判断机会不相匹配聪明的你一定可以想到解决这个问题只需要把向右侧的次数减少或者让向右侧也只需要一次判定所以解决问题的思路就这两种调整前后的宽度适当加长缩短左右侧的数组pro版统一沿两个方向深入所需的比较次数比如说都统一为一次promax版比如像这样像第一种pro版本情况就不细说了大致可以把这个数组六四分这种样子让mid(leftright)∗6/10mid(leftright)*6/10mid(leftright)∗6/10总之是让右边占的比例小一点总体效果就会更均衡如果用斐波那契数列弄一下的话效果会更好总之是一个进步不过需要注意的是如果完全不要右边那就变成从后往前的顺序查找了那样就得不偿失了对于第二种promax版的情况其实和前面的二分查找思路基本类似判断它是否在左侧如果targetnum[mid]那就让right到mid-1因为此时mid!target,否则targetnum[mid]关于target返回值是left因为最后一定要走targetnum[mid]这里target如果存在那一定是在左边这个关于int mid left (right - left 1) / 2;是为了让他向后取整防止找数组中最后一个数的情况比如在{3,5}里找5带进去试一下就会发现它会往后取整这样就可以取到数组中最后一个元素了了intbinsearch2(int*nums,intnumsSize,inttarget){intleft0;intrightnumsSize-1;while(leftright){intmidleft(right-left1)/2;if(targetnums[mid]){rightmid-1;}else{leftmid;}}return(targetnums[left])?left:-1;}intbinsearch2(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmidleft(right-left1)/2;if(targetnums[mid]){rightmid-1;}else{leftmid;}}return(targetnums[left])?left:-1;}1.4 总结二分查找在逻辑上很容易理解但是只有真敲一遍才会出现各种小问题建议理解后自己敲一遍为山九仞功亏一篑。如果看完没学会那我很抱歉是我标题党了不要来打我1.5完整测试代码完整测试代码#includestdio.h#includewindows.hintsearch(int*nums,intnumsSize,inttarget){for(inti0;inumsSize;i){if(nums[i]target){returni;}}return-1;}intbinsearch(int*nums,intnumsSize,inttarget){intleft0;intrightnumsSize-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){rightmid-1;}elseif(nums[mid]target){leftmid1;}else{returnmid;}}return-1;}intbinsearch2(int*nums,intnumsSize,inttarget){intleft0;intrightnumsSize-1;while(leftright){intmidleft(right-left1)/2;if(targetnums[mid]){rightmid-1;}else{leftmid;}}return(targetnums[left])?left:-1;}intmain(){SetConsoleOutputCP(65001);inta[]{2,4,5,7,8,9,12};intnsizeof(a)/sizeof(a[0]);// 计算数组长度inttargets[]{7,2,12,6};// 测试用例存在和不存在intmsizeof(targets)/sizeof(targets[0]);printf(Array: );for(inti0;in;i)printf(%d ,a[i]);printf(\n\n);for(intj0;jm;j){inttargettargets[j];intindex1search(a,n,target);intindex2binsearch(a,n,target);intindex3binsearch2(a,n,target);printf(目标值%d\n,target);printf( 线性搜索结果%d\n,index1);printf( 二分搜索结果%d\n,index2);printf( 二分搜索promax结果%d\n,index3);printf(\n);}return0;}