JAVA-二分法查找算法总结

ゞ浴缸里的玫瑰 2022-06-15 02:58 174阅读 0赞

二分查找算法：  
二分查找算法也叫折半查找算法。  
优点：1.比较次数少 2.查找速度快 3.平均性能好  
缺点：1.待查表需要是有序的 2.插入、删除困难  
算法原理：  
假设对于一个按序排列的列表a，需要查找的键值为：key，数组列表中间那个元素对应的索引为：mid  
初始化该列表起始元素的索引：low，最后一个元素的位置索引为：high=a.length-1。  
步骤：  
输入：  
1.数组a  
2.要查找的对象key  
输出：要查找的对象在数组、列表中所对应的索引。  
步骤一：将按序排列的数组列表a的中间的数a\[mid\]与要查找的键值key比较  
步骤二：如果a\[mid\]>key，则数组列表的最后一个元素索引high=mid-1，如果a\[mid\]

public class A09 {
        //二分查找非递归的程序实现
        public static int rank(int a[],int key){
            int low=0;
            int high=a.length-1;
            int mid=low+(high-low)/2;
    
            while(low<high){
                if(a[mid]>key)
                    high=mid-1;
                if(a[mid]<key)
                    low=mid+1;
                else 
                    return mid;
            }
            return -1;//静态方法是顺序执行的，结束执行的语句应该放在最后
    
        }

**递归实现二分查找：**
    class lpq01{
        //二分查找的递归实现
        public static int factor(int key,int a[]){
            return factor(key,a,0,a.length-1);
        } 
        public static int factor(int key,int a[],int lo,int hi){
            if(lo>hi)
                return -1;
            int mid=lo+(hi-lo)/2;
            if(a[mid]>key)
                return factor(key,a,lo,mid-1);
            if(a[mid]<key)
                return factor(key,a,mid+1,hi);
            else
                return  mid;
        }
    }

算法要求：  
1.必须采用顺序存储结构  
2.必须按照关键字大小有序排列  
算法复杂度：  
假设数组元素个数为n，则算法复杂度为:O(logn)  
注：二分查找存在一个BUG，就是无法查到第一个和最后一个元素的值，可以在比较到最后两个数后再次判断到底哪个和要查找的数相等。