2

みなさん、こんにちは。

私の問題は、バイナリ検索を使用して ArrayList を検索し、オブジェクトを追加する正しい場所を見つけて、リストが順番どおりになるようにする必要があることです。これは宿題なので、コレクションの並べ替えは使用できません。リストに検索対象の項目が含まれているかどうかを示すブール値メソッドを正しく実装しました。そのコードはここにあります：

    public static boolean search(ArrayList a, int start, int end, int val){
    int middle = (start + end)/2;
    if(start == end){
        if(a.get(middle) == val){
            return true;
        }
        else{
            return false;
        }
    }
    else if(val < a.get(middle)){
        return search(a, start, middle - 1, val);
    }
    else{
        return search(a, middle + 1, end, val); 
    }
}

私がする必要があるのは、このメソッドを使用して、数値がリストに既に存在するかどうかを確認することです。それが false を返す場合は、別のバイナリ検索を使用して、リスト内のどこに数値 (val) を配置する必要があるかを調べる必要があります。どんな助けでも大歓迎です、ありがとう!!!

ジャスティン

4

2 に答える 2

3

true または false を返す代わりに、検索の最後のインデックスを返すことができます。したがって、値がリストにない場合は、最後にアクセスしたインデックスを返し、値がそのインデックスの現在の値より小さいか大きいかを確認し、それに応じて新しい値を追加します。

于 2013-03-17T23:46:40.020 に答える
2

ブール値を返す代わりに、すでに見つけた値の位置を返す必要があります。繰り返しの解決策は問題ありませんが、非常に大きなリストの場合、結果を見つけるのは問題になります。反復を使用する代わりに、ループベースのソリューションを実装してみてください。私はあなたがそれを理解するのを助ける小さなデモを作成しました：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SourceCodeProgram {

    private List<Integer> integers = new ArrayList<Integer>();

    public static void main(String argv[]) throws Exception {
        SourceCodeProgram test = new SourceCodeProgram();
        test.addIntegerToSortedListVerbose(10);
        test.addIntegerToSortedListVerbose(2);
        test.addIntegerToSortedListVerbose(11);
        test.addIntegerToSortedListVerbose(-1);
        test.addIntegerToSortedListVerbose(7);
        test.addIntegerToSortedListVerbose(9);
        test.addIntegerToSortedListVerbose(2);
        test.addIntegerToSortedListVerbose(5);
        test.addIntegerToSortedListVerbose(1);
        test.addIntegerToSortedListVerbose(0);
    }

    private void addIntegerToSortedListVerbose(Integer value) {
        int searchResult = binarySearch(integers, value);
        System.out.println("Value: " + value + ". Position = " + searchResult);
        integers.add(searchResult, value);

        System.out.println(Arrays.toString(integers.toArray()));
    }

    private int binarySearch(List<Integer> list, Integer value) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            Integer midVal = list.get(mid);
            int cmp = midVal.compareTo(value);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return low;
    }
}

プログラムプリント：

Value: 10. Position = 0
[10]
Value: 2. Position = 0
[2, 10]
Value: 11. Position = 2
[2, 10, 11]
Value: -1. Position = 0
[-1, 2, 10, 11]
Value: 7. Position = 2
[-1, 2, 7, 10, 11]
Value: 9. Position = 3
[-1, 2, 7, 9, 10, 11]
Value: 2. Position = 1
[-1, 2, 2, 7, 9, 10, 11]
Value: 5. Position = 3
[-1, 2, 2, 5, 7, 9, 10, 11]
Value: 1. Position = 1
[-1, 1, 2, 2, 5, 7, 9, 10, 11]
Value: 0. Position = 1
[-1, 0, 1, 2, 2, 5, 7, 9, 10, 11]
于 2013-03-18T00:14:10.767 に答える