二分查找算法(Java)

二分查找算法(Java)1.二分查找算法思想:将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x2.时间复杂度:匹配k次后,剩下的元素个数为:n/(2^k)根据n/(2^k)=1,即可求出时间复杂度O(log2n),以2为底,n的对数.3.算法要求:(1)待查询的序列必须按关键字大小排列;(2)待查询的序列必须采用顺序存储结构;4.优缺点

1.二分查找算法思想:

将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x

2.时间复杂度:

匹配k次后,剩下的元素个数为: n/(2^k)
根据 n/(2^k) >=1 , 即可求出时间复杂度 O(log2 n) ,以2为底, n的对数.

3.算法要求:

(1)待查询的序列必须按关键字大小排列;
(2)待查询的序列必须采用顺序存储结构;

4.优缺点:

优点:比较次数少,查找速度快;
缺点:必须采用顺序存储结构,插入删除困难;

5.算法的递归实现:

6.算法的非递归实现:

public class Main1 {

    public static int binarySearch(int []a,int num){
        int len=a.length;
        int high=len-1;
        int low=0;
        while(low<=high){
            int mid=(high+low)>>1;
            if(a[mid]==num)
                return mid;
            else if(a[mid]<num)
                low=mid+1;
            else
                high=mid-1;
        }
        return -1;
    }

    public static void main(String args[]){
        int []a={
  
  1,10,30,34,40,45,59};
        int index=Main1.binarySearch(a, 30);
        System.out.println(index);
    }
}

7.算法的递归实现:

public class Main1 {
    public static int binarySearch_(int []a,int low, int high,int num){
        if(low<=high){
            int mid=(low+high)>>1;
            if(a[mid]==num)
                return mid;
            else if(a[mid]<num)
                low=mid+1;
            else
                high=mid-1;
            return binarySearch_(a,low,high,num);
        }else
            return -1;
    }

    public static void main(String args[]){
        int []a={
  
  1,10,30,34,40,45,59};
        int index=Main1.binarySearch_(a, 0,a.length-1,3);
        System.out.println(index);
    }
}

今天的文章二分查找算法(Java)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/9875.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注