0

如何在 java 中仅使用 1 个参数在 int 数组中实现递归二进制搜索？它试过了，但我的代码不起作用。我实现了一个类，它的实例是具有数组和计数变量的对象，以检测数组中有多少元素。知道如何仅使用 1 个参数来实现递归二进制搜索吗？

public class LinearSortedArray {
    int count;
    int[] a;

    public LinearSortedArray() {
        count = 0;
    }

    public LinearSortedArray(int size) {
        count = 0;
        a = new int[size];
    }

    public static int[] copyingMethod(int startPoint, int endPoint,
            LinearSortedArray arrayObj) {
        int[] copyingArray = new int[endPoint - startPoint];
        int j = startPoint;
        for (int i = 0; i < copyingArray.length; i++) {
            copyingArray[i] = arrayObj.a[j];
            j++;
        }
        return copyingArray;
    }

    public int binarySearchRec(int x) {
        if (count == 0) {
            return -1;
        }
        int pivot = count / 2;
        LinearSortedArray newArrayObj;
        if (x > a[pivot]) {
            newArrayObj = new LinearSortedArray(count - pivot);
            newArrayObj.count = newArrayObj.a.length;
            newArrayObj.a = copyingMethod(pivot, count, this);

            for (int i = 0; i < newArrayObj.a.length; i++) {
                System.out.print(newArrayObj.a[i]);
                System.out.print(" ");
            }
            System.out.println();
            return pivot + newArrayObj.binarySearchRec(x);
        } else if (x < a[pivot]) {
            newArrayObj = new LinearSortedArray(pivot);
            newArrayObj.count = newArrayObj.a.length;
            newArrayObj.a = copyingMethod(0, pivot, this);
            for (int i = 0; i < newArrayObj.a.length; i++) {
                System.out.print(newArrayObj.a[i]);
                System.out.print(" ");
            }
            System.out.println();
            return newArrayObj.binarySearchRec(x);
        } else {
            return pivot;
        }
    }
}

PS：数组已经排序

4

2 回答 2

0

您可以使用Value Object Pattern设计一个单参数，在其中传递一个“包装器”对象，但该对象有很多字段。

例如：

class SearchParams {
    int target;
    int start;
    int end;  
    SearchParams(t, s, e) {
        target = t;
        start = s;
        end = e'
    }
}

int search(SearchParams params) {
    // some impl
    return search(new SearchParams(params.target, a, b));
}

从技术上讲，这是一个参数。虽然它可能不符合规则的精神。

于 2013-10-12T01:10:25.967 回答
0

二分搜索确实需要一个范围和一个目标值——所以如果你只传递一个参数，这必须是目标，并且它必须封装数组和范围。

public class ArraySegment {
    protected int[] array;
    protected int boundLo;
    protected int boundHi;

    public class ArraySegment (int[] array) {
        // entire array.
        this( array, 0, array.length);
    }
    public class ArraySegment (int[] array, int lo, int hi) {
        this.array = array;
        this.boundLo = lo;
        this.boundHi = hi;
    }

    public int binarySearch (int target) {
        if (boundHi <= boundLo) {
            return -1;         // Empty;  not found.
        }

        int pivot = (boundLo + boundHi) / 2;
        int pivotEl = array[ pivot];
        if (target == pivotEl) {
            return pivot;      // Found!
        }
        if (target < pivotEl) {
            // recurse Left of pivot.
            ArraySegment sub = new ArraySegment( array, boundLo, pivot);
            return sub.binarySearch( target);
        } else {
            // recurse Right of pivot.
            ArraySegment sub = new ArraySegment( array, pivot, boundHi);
            return sub.binarySearch( target);
        }
    }
}

你应该返回什么样的结果有点问题 - 像这样提出的问题没有一个好的答案，因为“整数索引”有点违背 ArraySegment/ 范围包装器的目的，并返回一个 ArraySegment 包含只有找到的值也相当无用。

PS：你真的不应该复制数组或其内容，只是将循环引用传递给该数组上的范围。Likejava.lang.String是字符数组上的一个范围。

于 2013-10-12T01:12:14.323 回答