8

私は大学の休みを利用して、プログラミング アルゴリズムを通じて Java の練習をしています。私がコード化したアルゴリズムの 1 つは二分探索でした。

public class BinarySearch {

    private static int list[] = {3, 6, 7, 8, 9, 10};

    public static void main(String[] args) {
        BinarySearch b = new BinarySearch();
        b.binarySearch(list);

    }

    public void binarySearch(int[] args) {
        System.out.println("Binary search.");

        int upperBound = args.length;
        int lowerBound = 1;
        int midpoint = (upperBound + lowerBound) / 2;
        int difference = upperBound - lowerBound;

        int search = 7;

        for (int i = 0; i < args.length; i++) {
            if (search < args[midpoint - 1] && difference != 1) {
                upperBound = midpoint - 1;
                midpoint = upperBound / 2;
            } else if (search > args[midpoint - 1] && difference != 1) {
                lowerBound = midpoint + 1;
                midpoint = (lowerBound + upperBound) / 2;

            } else if (search == args[midpoint - 1]) {
                midpoint = midpoint - 1;

                System.out.println("We found " + search + " at position " + midpoint + " in the list.");
                i = args.length;
            } else {
                System.out.println("We couldn't find " + search + " in the list.");
                i = args.length;
            }
        }
    }
}

私は、自分がコーディングしたアルゴリズムに代わる、よりクリーンで効率的な二分探索アルゴリズムを書きたいと思っています。私が理解している数値で階乗を行う場合など、再帰がどのように使用されるかの例を見てきました。しかし、この複雑なものをコーディングするとき、私はそれを自分の利点に使用する方法について混乱しています。したがって、私の質問は、二分探索アルゴリズムをコーディングするときに再帰をどのように適用するかです。また、二分探索に関係のないものであっても、再帰スキルを完璧にするためのヒントがあれば、お気軽に投稿してください。

4

8 に答える 8

2

以下は、ここから抽出されたコード サンプルです。

public class BinarySearch {

    public boolean find(int[] sortedValues, int value) {
        return search(sortedValues, value, 0, sortedValues.length - 1);
    }

    private boolean search(int[] sorted, int value, int leftIndex, int rightIndex) {

        // 1. index check
        if (leftIndex > rightIndex) {
            return false;
        }

        // 2. middle index
        int middle = (rightIndex + leftIndex) / 2;

        // 3. recursive invoke
        if (sorted[middle] > value) {
            return search(sorted, value, leftIndex, middle - 1);
        } else if (sorted[middle] < value) {
            return search(sorted, value, middle + 1, rightIndex);
        } else {
            return true;
        }
    }
}

上記の二分探索の実装に対する以下のテスト ケースの実装は、参照リンクでも確認できます。

1. shouldReturnFalseIfArrayIsEmpty()
2. shouldReturnFalseIfNotFoundInSortedOddArray()
3. shouldReturnFalseIfNotFoundInSortedEvenArray()
4. shouldReturnTrueIfFoundAsFirstInSortedArray()
5. shouldReturnTrueIfFoundAtEndInSortedArray()
6. shouldReturnTrueIfFoundInMiddleInSortedArray()
7. shouldReturnTrueIfFoundAnywhereInSortedArray()
8. shouldReturnFalseIfNotFoundInSortedArray()
于 2013-11-03T09:16:25.323 に答える
0

インデックスは返されませんが、これは少なくともコレクションに何かがあるという「はい」または「いいえ」の考えを返します。

public static boolean recursive(int[] input, int valueToFind) {
    if (input.length == 0) {
        return false;
    }

    int mid = input.length / 2;
    if (input[mid] == valueToFind) {
        return true;
    } else if (input[mid] > valueToFind) {
        int[] smallerInput = Arrays.copyOfRange(input, 0, mid);
        return recursive(smallerInput, valueToFind);
    } else if (input[mid] < valueToFind) {
        int[] smallerInput = Arrays.copyOfRange(input, mid+1, input.length);
        return recursive(smallerInput, valueToFind);
    }

    return false;
}
于 2016-12-14T00:19:44.817 に答える