欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法与数据结构(13)—— 二分查找(递归与非递归)

程序员文章站 2022-06-17 19:46:28
...

递归

private static int find(Comparable[] arr, int l, int r, Comparable target){
        if(l > r) return -1;

        int mid = (r-l)/2 + l;

        if(arr[mid].compareTo(target) == 0)
            return mid;
        else if(arr[mid].compareTo(target) > 0)
            return find(arr, l, mid-1, target);
        else
            return find(arr, mid+1, r, target);
    }

    public static int find(Comparable[] arr, Comparable target){
        return find(arr, 0, arr.length-1, target);
    }

非递归

public static int find(Comparable[] arr, Comparable target){
        // 在arr[l...r]之中查找target
        int l = 0, r = arr.length - 1;
        while(l <= r){

            int mid = (r - l)/2 + l;

            if(arr[mid].compareTo(target) == 0){
                return mid;
            }else if(arr[mid].compareTo(target) > 0){
                r = mid - 1;
            }else if(arr[mid].compareTo(target) < 0){
                l = mid + 1;
            }
        }

        return -1;
    }


算法与数据结构(13)—— 二分查找(递归与非递归)



相关标签: 递归 二分