Java怎么实现二分查找的变种
小编给大家分享一下Java怎么实现二分查找的变种,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
我们提供的服务有:成都网站建设、成都做网站、微信公众号开发、网站优化、网站认证、辉南ssl等。为上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的辉南网站制作公司
Java的优点是什么
1. 简单,只需理解基本的概念,就可以编写适合于各种情况的应用程序;2. 面向对象;3. 分布性,Java是面向网络的语言;4. 鲁棒性,java提供自动垃圾收集来进行内存管理,防止程序员在管理内存时容易产生的错误。;5. 安全性,用于网络、分布环境下的Java必须防止病毒的入侵。6. 体系结构中立,只要安装了Java运行时系统,就可在任意处理器上运行。7. 可移植性,Java可以方便地移植到网络上的不同机器。8.解释执行,Java解释器直接对Java字节码进行解释执行。
具体内容如下
普通二分查找:
先回顾一下普通的二分查找
注意:二分查找有这样一个问题:当数组中数有重复时,比如 {3,3,3,3} 这个数组,二分查找3时,返回的是arr[1],也就是说二分查找并不会返回3第一次出现的位置0。
public class BinarySearch { public static> int search(T arr[], T value) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = (left & right) + ((left ^ right) >> 1); if (arr[mid].compareTo(value) == 0) { return mid; } else if (arr[mid].compareTo(value) > 0) { right = mid - 1; } else { left = mid + 1; } } return -1; } public static void main(String[] args) { Integer[] arr = new Integer[]{1, 3, 3, 6, 7, 9}; //-1 System.out.println(search(arr, 0)); //0 System.out.println(search(arr, 1)); //5 System.out.println(search(arr, 9)); //-1 System.out.println(search(arr, 10)); //2 System.out.println(search(arr, 3)); } }
二分变种:findFirst函数
在普通二分查找中,在[left....right]左闭右闭区间中查找,如果找到了值为value的元素就认为找到了。而在这个findFirst函数中就不是如此,在[left....right]左闭右闭区间中查找,当找到值等于value的元素后,不是让right = mid - 1,而是让right = mid,继续在[left....right]左闭右闭区间中查找。最终left== right时就退出循环。
退出循环后可能找到了value值,也有可能是循环遍历完整个数组后都没找到value,而退出循环。
所以退出循环后还要在判断一下是那种情况。
public class BinarySearch { public static> int findFirst(T arr[], T value) { int left = 0; int right = arr.length - 1; //当left>=right时退出,这里的“=”情况与二分不同 while (left < right) { int mid = (left + right) >> 1; if (arr[mid].compareTo(value) < 0) { left = mid + 1; } else { right = mid; } } // 上面循环遍历完后。是找到了value值?还是没找到value值?判断一下。 if (arr[left] == value) { return left; } else { return -1; } } public static void main(String[] args) { Integer[] arr = new Integer[]{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9}; //-1 System.out.println(findFirst(arr, 0)); //0 System.out.println(findFirst(arr, 1)); //12 System.out.println(findFirst(arr, 9)); //-1 System.out.println(findFirst(arr, 10)); //1 System.out.println(findFirst(arr, 3)); } }
二分变种:fewer函数
介绍
给定一个数组,和一个变量value,从数组中找出值最接近value值而且比value小的那个数。比如 arr = {11,22,22,33 ,33,33,44,54} value = 33。 22最接近value,而且比value小。
所以答案是2 ( 22在数组arr中的下角标 ) 。
如果没找到比value小的数,那么输出 -1。
解决思路
用二分查找方法。每次用 arr[mid] 来与value进行比对。小、等于,去左边找;大,去右边找。可能上一句的“等于”的情况你不太理解。普通二分查找是找出arr[mid] == value,而fewer函数是为了找出比value小的数,所以尽管arr[mid] == value,还得继续去左边找更小的值。
例子
代码
public class BinarySearch { public static> int fewer(T arr[], T value) { int left = 0; int right = arr.length - 1; //当left > right 时退出 while (left <= right) { int mid = (left & right) + ((left ^ right) >> 1); if (value.compareTo(arr[mid]) <= 0) { right = mid - 1; } else { left = mid + 1; } } return right; } public static void main(String[] args) { Integer[] arrF = new Integer[]{21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; //3 System.out.println(fewer(arrF, 30)); } }
以上是“Java怎么实现二分查找的变种”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!
新闻标题:Java怎么实现二分查找的变种
转载来于:http://pwwzsj.com/article/psgspc.html