二分查找算法的两种实现方式

二分查找的条件是对一组有序数组的查找,这一点很容易忘记,在使用二分查找的时候先要对数组进行排序。

先说一下二分查找的思路:一个有序数组,想要查找一个数字key的下标,首先算出中间下标mid,利用mid把这个数组分为两半,前一半从下标0到mid-1,后一半从mid+1到数组最后一个元素(下标是数组长度减一)。把这个查找的元素key和数组下标为mid的元素进行比较,也就是和中间那个元素进行比较,如果比这个元素的小那么把查找范围缩小到原数组的前一半(把查找下标缩短到0到mid-1),如果比中间mid下标元素大那么范围就是后半部分(下标为mid+1到数组长度减一),这样来回反复取中间比较最后就会定位到要查找元素key的下标。

二分查找有两种实现方式:

非递归实现
递归实现
在jdk源码中Arrays数组工具类中已经封装好了二分查找算法,不会写可以看看源码,源码实现的方式肯定是效率比较高的。比如计算数组中间下标mid利用移位运算。

非递归实现:
/**

 * @param array 操作数组
 * @param key 查找元素
 * @return 元素下标
 */
public static int binSearch(int[] array,int key){
    int start=0;
    int mid;
    int end=array.length-1;
    while(start<=end){
        mid=(end-start)/2+start;
        if(key<array[mid]){
            end=mid-1;
        }
        else if(key>array[mid]){
            start=mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}

递归实现:
/**

 * @param array 操作数组
 * @param key 查找元素
 * @param start 开始下标
 * @param end 结束下标
 * @return 元素下标
 */
public static int binSearch1(int[] array,int key,int start,int end){
    int mid=(end-start)/2+start;
    if(key==array[mid]){
        return mid;
    }
    else if(start>=end){
        return -1;
    }
    else if(key>array[mid]){
        return binSearch1(array,key,mid+1,end);
    }
    else if(key<array[mid]){
        return binSearch1(array,key,start,mid-1);
    }
    return -1;
}

作者:In_new
来源:CSDN
原文:https://blog.csdn.net/qq_38663729/article/details/78946726
版权声明:本文为博主原创文章,转载请附上博文链接!

打赏 支付宝打赏 微信打赏

未经允许不得转载!

评论列表 0

访客
取消