摘要:写二分法时需要判断循环何时终止,如果每次都是,,会导致循环无法终止,所以此处用了。递归实现二分法目标数组,目标值,左边界,右边界输入的数组是
//非递归实现二分法
public class Jianzhi{ public static void main (String[] args){ int[] num = {1,2,3,4,5,100}; int m = find(num , 5) ; System.out.println(m); } public static int find(int[] list , int m ){ if(list == null ){ System.out.println("输入的数组长度出错。") ; }else if(list.length ==1 ){ //如果传入的数组只有一个数字 int n = list[0]==m?0:-1 ; return n ; }else { int left = 0 ; int right = list.length-1 ; while(left <= right){ int mid = (left + right)/ 2 ; if(list[mid]==m){ return mid ; }else if (list[mid]m){ right = mid - 1 ; } } System.out.println("未在数组中找到数字"+m); } return -1 ; } }
//注意: 1.需要把mid放入循环中,不能放在循环体外,因为每次都要把mid赋值给left或者right如果放在外面每次赋值的数都一样会死循环。
// 2.写二分法时需要判断循环何时终止,如果每次都是left=mid,right=mid,会导致循环无法终止
// ,所以此处用了left=mid+1 right=mid-1 。这样做还有一个好处:发现mid不是所要找的数时,就直接舍弃,让left和right不指向这个节点。
——————————————————————————————————————————————————
//递归实现二分法
public class Jianzhi{ // (目标数组,目标值,左边界,右边界) public static int find(int[] list , int m ,int begin , int end) { if(list == null){ System.out.println("输入的数组是null"); return -1 ; } if(list.length == 1 ){ return list[0]==m?0:-1 ; } if(begin > end){ return -1 ; } int mid = (begin + end) / 2 ; if(list[mid] == m){ return mid ; }else if (list[mid] < m ){ return find(list , m ,mid+1 , end ); }else if (list[mid] > m ){ return find(list , m , begin , mid-1 ); } return -1 ; } public static void main (String[] args){ int[] num = {1,2,3,4,5,100}; int m = find(num , 1,0,num.length-1) ; System.out.println(m); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/71375.html
摘要:二分查找的定义二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。算法的要求从上面的定义我们可以知道,满足该算法的要求必须如下两点必须采用顺序存储结构。 showImg(https://segmentfault.com/img/remote/1460000016466416?w=800&h=191); 二分查找的...
摘要:数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合,是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。 项目地址 https://github.com/m9rco/algo... 每周最少一更,求出题,求虐待 At least once a week, ask for problems and abuse 简...
摘要:数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合,是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。 项目地址 https://github.com/m9rco/algo... 每周最少一更,求出题,求虐待 At least once a week, ask for problems and abuse 简...
摘要:数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合,是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。 项目地址 https://github.com/m9rco/algo... 每周最少一更,求出题,求虐待 At least once a week, ask for problems and abuse 简...
阅读 2458·2021-09-28 09:36
阅读 3597·2021-09-22 15:41
阅读 4388·2021-09-04 16:45
阅读 1957·2019-08-30 15:55
阅读 2847·2019-08-30 13:49
阅读 825·2019-08-29 16:34
阅读 2370·2019-08-29 12:57
阅读 1679·2019-08-26 18:42