微网站建设哪家优惠,编辑wordpress的代码,开发一个公众号大概需要多少钱,信息造价网文章目录 前言1. 基本查找2. 二分查找与分治2.1 循环的方式2.2 递归的方式 3. 元素中的重复的二分查找总结 前言 提示#xff1a;有些人#xff0c;远看是灯塔#xff0c;靠近是悬崖。 --任明信《别人》 二分查找是非常重要的算法之一#xff0c;不仅要掌握#xff0c;更要… 文章目录 前言1. 基本查找2. 二分查找与分治2.1 循环的方式2.2 递归的方式 3. 元素中的重复的二分查找总结 前言 提示有些人远看是灯塔靠近是悬崖。 --任明信《别人》 二分查找是非常重要的算法之一不仅要掌握更要了解相关变形题目。 查找可以很简单也可以很复杂散列、动态规划等高难度算法都可以视为查找问题这里我们先看看一些基础问题。
常见的查找算法有顺序查找、二分查找、插值查找斐波那契查找、树表查找、分块查找、哈希查找等等。其实二分查找、插值查找以及斐波那契查找都可以归为一类----插值查找。插值查找和斐波那契额查找是在二分查找的基础上的优化查找算法。
这些算法中最重要的无疑是Hash查找和二分查找。Hash我们前面的章节已经接触过了这里我们重点就来谈谈二分查找及其变形问题。
二分查找的价值不限于此请记住凡是涉及到排好序的地方查找的都可以考虑采用二分查找来优化查找效率。不一定全局有序只要某部分有序也行针对这一部分进行二分查找这是很多题目优化查找的重要途经。
除了二分外还有插值查找、斐波那契查找分块查找等多种常见的算法本质上仍是对二分的进一步扩展。我们知道二分就是每次只取一半但是在有些场景下我们大致知道数据的位置了就不必折半取1/33/4这样不是也可以吗当然可以为了方便通用性插值查找使用的公式是
mid low (key - a[low])/(a[high] - a[low])*(high - low)这个来源自牛顿发明的积分公式如果不懂可以找数学老师补补课
分块查找是折半查找和顺序查找的一种改进方法分块查找由于只要求索引表示有序的对块内节点没有排序要求因此特别适合节点动态变化的情况。分块查找要求把一个数据分为若干块每一块里面的元素可以是无序的但是块与块之间的元素需要是有序的。即第一块中的任意元素的关键字都必须小于第二块中的任意元素的关键字第二块中的任意元素又都必须小于第三块中的任意元素一次类推。
1. 基本查找
查找算法中顺序查找算是最简单的了无论是有序还是无序的都可以也不需要排序只需要一个一个的对比就可以了但是这样的话效率太低了我们看下代码
public static int search(int[] nums,int key) {for(int i 0; i nums.length; i){if(nums[i] key){return i;}}return -1;
}顺序查找是最简单的一种查找算法对数据的要求也随意不需要排序即可查找。后面我们会介绍二分查找插值查找、斐波那契查找都是基于已经排序过的数据。
2. 二分查找与分治
在计算机科学中分治法是一种很重要的算法。字面上的解释就已经很通俗了“分而治之”就是把一个复杂的问题分成两个或者更多的相同或者相似的子问题再把子问题分成更小的子问题…直到最后问题可以简单的直接求解原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础比如二分搜索排序算法快速排序、并归排序等等…
任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关。问题的规模越小越容易直接求解解题所需要的计算时间也越少。例如对n个元素进行排序当n1时不需要计算当n 2时只需要比较一次即可排序好n 3时只需要比较3次也可以知道结果…而当n较大时问题就不是那么容易处理了。要想直接解决一个规模较大的问题有时是相当困难的。
二分查找就是将中间结果与目标进行比较一次去掉一半因此二分查找可以说是最简单也最经典的分治了。 二分查找不管是循环还是递归方式我觉得都很重要你要达到闭着眼1分钟写出来的地步。
这里补充一个问题分治和递归是一回事吗很显然不是。这两者完全不同的思想二分查找是分治思想我们可以采用递归或者循环来实现但是很多递归问题不一定可以采用分治解决因此完全不是一回事。
2.1 循环的方式
常见的使用循环的方式来实现二分查找如下你打几分 /*** 循环实现二分查找** param array* param low* param high* param target* return*/public static int binarySearch1(int[] array, int low, int high, int target) {// 循环遍历 小于等于while(low high){// 取中间值int mid (low high) / 2;if (array[mid] target){return mid;}else if (array[mid] target){// 由于array[mid]不是目标值因此在下一次循环中需要排除high mid - 1;}else{// 由于array[mid]不是目标值因此在下一次循环中需要排除low mid 1;}}return -1;}在具体的操作中可能又很多中形式包括循环体中的high mid - 1和low mid 1也有很多方式这里需要与if后面的条件配合我们不要给自己添麻烦在理解的基础上熟记这种方式就可以了。
如果代码写成这样可能刚刚及格70以为你有一个重要的细节没有处理在计算机中除的效率是很低的一半会采用位移的方式替代也就是如下
将int mid low high) / 2
改成int mid low high 1;如果这样的话可以加10分但是也是又问题的。面试官会继续问下去你考虑到又什么问题嘛这里又个漏洞☠️就是low和high很大的话lowhigh就可能溢出了因此我们可以改成这样写
int mid low (high - low) 1你觉得这样就对了大错特错你测试的时候就会出现问题不信你试试。
因为这里的位移运算 优先级比加减要低所以上面的代码就会变成这个样子
int mid (low (high - low)) 1很显眼这个不可能达到正确结果的解决方法也很简单加上括号就可以了所以我们的最终代码应该是这样
/*** 循环实现二分查找** param array* param low* param high* param target* return*/public static int binarySearch1(int[] array, int low, int high, int target) {// 循环遍历 小于等于while(low high){// 取中间值 用左移代替除int mid low ((high - low) 1);if (array[mid] target){return mid;}else if (array[mid] target){// 由于array[mid]不是目标值因此在下一次循环中需要排除high mid - 1;}else{// 由于array[mid]不是目标值因此在下一次循环中需要排除low mid 1;}}return -1;}这样的话面试官就提不出什么问题了而且上面的这个优先级问题很多人只是理解了但是没有做过测试知其然不知所以然。因此很多面试官也不会注意这里会有死循环的情况。当然这里还没有考虑到元素重复的情况这个以后讨论。
2.2 递归的方式
递归就很简单了这里我们直接看代码 /*** 方法二递归方式实现** param array* param low* param high* param target* return*/public static int binarySearch2(int[] array, int low, int high, int target) {// 终止条件 注意这里是ifif (low high){// 提高int mid low ((high - low) 1);if (array[mid] target){return mid;}else if(array[mid] target){// 由于array[mid]不是目标值因此在下一次循环中需要排除return binarySearch2(array, low, mid - 1, target);}else {// 由于array[mid]不是目标值因此在下一次循环中需要排除return binarySearch2(array, mid 1, high, target);}}// 表示没有找到return -1;} 这里的mid的计算和可能出现的问题与上面的是一样的。这也是面试体现基本功的亮点。如果写到这个程度的话已经接近满分了面试官也不会再说什么。
3. 元素中的重复的二分查找
假如在上面的基础上元素存在重复如果重复则找左侧的第一个请问该怎么处理这也是快手以前出现过。
这里的关键是找到目标结果之后不是返回而是继续向左移动。第一中也是最简单的方式找到相等的位置向左线性查找直到找到相应的位置。 /*** 重复元素二分找第一次出现的* param nums* param target* return*/public static int search1(int[] nums, int target) {if (nums null || nums.length 0){return -1;}int left 0;// 特殊情况提前处理if (nums[0] target){return 0;}int right nums.length - 1;while(left right){int mid left ((right - left) 1);if (nums[mid] target){right mid - 1;}else if (nums[mid] target){left mid 1;}else {// 注意判断 左移条件按while(mid ! 0 nums[mid] target){mid--;}// 思考一下这里为什么mid 1return mid 1;}}return -1;}当然这里也可以使用递归的方法(仅供参考 )
/*** 方法二仍然采用递归来找** param nums* param target* return*/public static int search2(int[] nums, int target) {if (nums null || nums.length 0)return -1;return binSearch2(nums, target, 0, nums.length - 1);}private static int binSearch2(int[] nums, int target, int left, int right) {if (left right)return -1;if (nums[left] target)return left;int mid left ((right - left) 1);if (nums[mid] target) {return binSearch2(nums, target, mid 1, right);} else if (nums[mid] target) {return binSearch2(nums, target, left, mid - 1);} else {return binSearch2(nums, target, left, mid);}}注意这里找到之后while循环之后为什么要mid1而不是返回mid–此时这里nums[mid]已经不是target了比如这个例子{1222233}。当target 3 while循环后退出nums[mid] 2 所以这必须要返回mid 1.
都写到这里面试官可能还会给你加个餐假如重复数量特别大此时是否可以对内层来一个二分呢当然可以我们可以找到相等的时候继续递归找到目标之后根据需求继续递归寻找这个可作为拓展⭐⭐⭐⭐⭐思考一下。 总结
提示二分查找mid写法优化重复值问题查找算法递归和分治
