java 二分法算法的实例
程序员文章站
2024-02-26 20:02:22
java 二分法算法的实例
1、前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
2、原理:将数组分为三部分,依次是中值(所谓的中值就是数组...
java 二分法算法的实例
1、前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
2、原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法
3、实现:
代码如下
package org.cyxl.algorithm.search; /** * 二分查找 * @author cyxl * */ public class binarysearch { private int rcount=0; private int lcount=0; /** * 获取递归的次数 * @return */ public int getrcount() { return rcount; } /** * 获取循环的次数 * @return */ public int getlcount() { return lcount; } /** * 执行递归二分查找,返回第一次出现该值的位置 * @param sorteddata 已排序的数组 * @param start 开始位置 * @param end 结束位置 * @param findvalue 需要找的值 * @return 值在数组中的位置,从0开始。找不到返回-1 */ public int searchrecursive(int[] sorteddata,int start,int end,int findvalue) { rcount++; if(start<=end) { //中间位置 int middle=(start+end)>>1; //相当于(start+end)/2 //中值 int middlevalue=sorteddata[middle]; if(findvalue==middlevalue) { //等于中值直接返回 return middle; } else if(findvalue<middlevalue) { //小于中值时在中值前面找 return searchrecursive(sorteddata,start,middle-1,findvalue); } else { //大于中值在中值后面找 return searchrecursive(sorteddata,middle+1,end,findvalue); } } else { //找不到 return -1; } } /** * 循环二分查找,返回第一次出现该值的位置 * @param sorteddata 已排序的数组 * @param findvalue 需要找的值 * @return 值在数组中的位置,从0开始。找不到返回-1 */ public int searchloop(int[] sorteddata,int findvalue) { int start=0; int end=sorteddata.length-1; while(start<=end) { lcount++; //中间位置 int middle=(start+end)>>1; //相当于(start+end)/2 //中值 int middlevalue=sorteddata[middle]; if(findvalue==middlevalue) { //等于中值直接返回 return middle; } else if(findvalue<middlevalue) { //小于中值时在中值前面找 end=middle-1; } else { //大于中值在中值后面找 start=middle+1; } } //找不到 return -1; } }
4、测试代码
package org.cyxl.algorithm.search.test; import org.cyxl.algorithm.search.binarysearch; import org.junit.test; public class binarysearchtest { @test public void testsearch() { binarysearch bs=new binarysearch(); int[] sorteddata={1,2,3,4,5,6,6,7,8,8,9,10}; int findvalue=9; int length=sorteddata.length; int pos=bs.searchrecursive(sorteddata, 0, length-1, findvalue); system.out.println("recursice:"+findvalue+" found in pos "+pos+";count:"+bs.getrcount()); int pos2=bs.searchloop(sorteddata, findvalue); system.out.println("loop:"+findvalue+" found in pos "+pos+";count:"+bs.getlcount()); } }
5、总结:这种查找方式的使用场合为已排序的数组。可以发现递归和循环的次数是一样的
以上就是java 二分法的实例详解,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇: Struts1和struts2的区别_动力节点Java学院整理
下一篇: 十三、JSP动作