前言
二分查找法又叫折半查找,是一种在有序数组中查找特定元素的搜索算法。
限制条件:二分查找法只适合于数组,而且是有序的数组。
原理:
假设有一个数组:{1,2,3,4,5,6,7,8,9,11,22}, 我们要在数组中找数值11在什么位置上,步骤如下:
第一步:我们先拿着11和中间数6比较,11明显比6大,说明11在7~22这段上。
第二步:我们拿着11和 7~22的中间数9比较,11还是比9大,说明在11~22这段上。
第三步:我们拿着11和11~22之间的中间数11比较,11等于11,说明我们找到了。
可能文字描述比较抽象,我弄了一个图来更直观一些。
看这张图再配合上面的解说,相信大家一定能明白这个原理,也相信大家一定能看得出只能有序数组才能适合二分查找法。下面我介绍一下代码:
代码中有详细的介绍,相信大家一定能够看懂,这里不就不过多介绍了。
时间复杂度
二分查找法,最好时间复杂度是:O(1),最坏时间复杂度是O(log2(n))。相比于上一章讲的线性查找时间复杂度O(n),性能提高了很多。
详细代码在我的码云中:/yydinfo/codes,大家可以下载运行一下。
结尾
好了今天就讲到这里吧,另外我想说的是:自己动手写是学数据结构和算法最好的捷径。大家如果不会的话,一定要在明白原理的基础上多写,写一遍记不住就写十遍,直到能很流畅的自己写下来为止,这样积累多了,量变总会质变的。
看的也这一章比前面几章难多了吧,后面我会逐渐的深入,把数据结构和算法一点一点的整理出来,希望大家关注了,要不退出这篇文章可能再也找不到小编了,这样小编会很伤心。
如果觉得《简单易懂的二分法查找法(java版) 网友:这次是真的记住了!》对你有帮助,请点赞、收藏,并留下你的观点哦!