Java— —用递归实现二分查找

发布时间:2023-02-20 10:00

递归实现二分查找(折半查找)

所谓二分查找,就是每次将数据分为两部分,找合适的那部分。

1.定义L,R左右指针分别指向我们数组的第一个和最后一个元素,key表示我们要查找的元素。

2.取(L+R)的中间值M=>(L+R)/ 2【此处我们也可以使用:L + (R-L) / 2 避免溢出】

3.如果我们key > M,我们就移动我们的L、R指针【将L移动到M+1;R指针不动】

4.反之,如果我们的key < M,我们就将【R指针移动到M - 1,L指针不动】

例如:
给定一个数组,我们要查找元素为6的索引:
Java— —用递归实现二分查找_第1张图片如果中间元素不满组足,我们直接从中间元素的前一个或者后一个查找=》避免重复查找(因为中间元素已经不等于key)
代码实现;

//二分查找
public class RecursionDemo04 {
//    private static  int count = 0;
    public static void main(String[] args) {
        //二分查找  折半查找
       int[] arr = {1,2,3,4,5,6,7,8,9,10};
       int index = binarySearch(arr,0,arr.length - 1,6);
//        System.out.println(count);
        System.out.println(index);
    }
    //在数组arr中 L~R区间内进行二分查找搜索
    private static int binarySearch(int[] arr, int L, int R, int key) {
//        count++;
        if(L > R){
            return -1;//元素不存在
        }
        int M = L + (R - L) / 2;
        if(arr[M] == key){
            return M;
        }
        if(arr[M] < key){
            return binarySearch(arr,M+1,R,key);
        }else{
            return binarySearch(arr,L,R-1,key);
        }
    }
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号