二分法的简单实现-------递归和非递归

tanglijun 发布于2019-08-16 12:36 / 1973人阅读

摘要：写二分法时需要判断循环何时终止，如果每次都是，，会导致循环无法终止，所以此处用了。递归实现二分法目标数组，目标值，左边界，右边界输入的数组是

//非递归实现二分法

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);
    }

}

GPU云服务器云服务器 java递归的二分法 python实现递归 java递归实现加法 python中的递归

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71375.html

PHP算法之二分查找

摘要：二分查找的定义二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。算法的要求从上面的定义我们可以知道，满足该算法的要求必须如下两点必须采用顺序存储结构。 showImg(https://segmentfault.com/img/remote/1460000016466416?w=800&h=191); 二分查找的...

Soarkey 2019-07-01 10:44 评论0 收藏0
用 PHP 的方式实现的各类算法合集

摘要：数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。项目地址 https://github.com/m9rco/algo... 每周最少一更，求出题，求虐待 At least once a week, ask for problems and abuse 简...

Karrdy 2019-06-28 13:32 评论0 收藏0
用 PHP 的方式实现的各类算法合集

摘要：数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。项目地址 https://github.com/m9rco/algo... 每周最少一更，求出题，求虐待 At least once a week, ask for problems and abuse 简...

pakolagij 2019-07-25 15:02 评论0 收藏0
用 PHP 的方式实现的各类算法合集

摘要：数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据的逻辑结构数据元素之间的相互关系称为逻辑结构。项目地址 https://github.com/m9rco/algo... 每周最少一更，求出题，求虐待 At least once a week, ask for problems and abuse 简...

leonardofed 2019-06-28 15:58 评论0 收藏0