0

私は、線形検索と二分検索の両方の手法で行われる比較の数を特定しようとしています。誰かがそれぞれの場合にループが発生した回数を印刷する方法を教えてもらえますか？たとえば、最初の配列で5を見つけるには、ループは1回だけ発生します。

       public static void main(String[] args) {
    // TODO code application logic here
    int[] values  = {5, 8, 6, 2, 1, 7, 9, 3, 0, 4, 20, 50, 11, 22, 32, 120};
    int[] valuesSorted  = {1, 2, 3, 4, 5, 8, 16, 32, 51, 57, 59, 83, 90, 104};
    DisplayArray(values);
    DisplayArray(valuesSorted);

    int index;
    index = IndexOf(1, values);
    System.out.println("1 is at values location " + index);
    index = IndexOf(120, values);

    System.out.println("120 is at values location " + index);

    index = BinaryIndexOf(104, valuesSorted);
    System.out.println("104 is at values Sorted location " + index);

    index = BinaryIndexOf(90, valuesSorted);
    System.out.println("90 is at values Sorted location " + index);       

}


public static int IndexOf(int value, int[] array)
{

    for (int i=0; i < array.length; i++)
    {

        if(array[i] == value)
            return i;

    }

    return -1;


}
public static int BinaryIndexOf(int value, int [] array)
{
    int start = 0;
    int end = array.length -1;
    int middle;

    while (end >= start)
    {
        middle = (start + end ) /2;
        if (array[middle]== value)
            return middle;
        if (array[middle]< value)
            start = middle + 1;
        else 
            end = middle - 1;
    }
    return -1;

}

public static void DisplayArray(int[] array)
{
    for (int a : array)
    {
        System.out.print(a + " ");
    }
    System.out.println();
}

}

4

2 に答える 2

6

線形検索の場合、次のようなことができます。

public static int IndexOf(int value, int[] array)
{
    for (int i=0; i < array.length; i++)
    {

        if(array[i] == value)
        {            
            System.out.println("Linear search: Number of comparisons = " + (i + 1));
            return i;
        }
    }

    return -1;
}

二分探索の場合は、次のようにします。

public static int BinaryIndexOf(int value, int [] array)
{
    int start = 0;
    int end = array.length -1;
    int middle;
    int loopCount = 0;
    while (end >= start)
    {
        loopCount++;
        middle = (start + end ) /2;
        if (array[middle]== value)
        {
            System.out.println("Binary search: Number of times looped = " + loopCount); 
            return middle;
        }
        if (array[middle]< value)
            start = middle + 1;
        else 
            end = middle - 1;
    }
    System.out.println("Binary search: Number of times looped = " + loopCount);
    return -1;

}
于 2012-11-12T02:09:13.027 に答える
0

簡単な方法の1つは、クラス内でカウンター変数を作成し、必要に応じて次のように操作することです。

private static int _loopCounter;

public static void main(String[] args) {
    // TODO code application logic here
    int[] values  = {5, 8, 6, 2, 1, 7, 9, 3, 0, 4, 20, 50, 11, 22, 32, 120};
    int[] valuesSorted  = {1, 2, 3, 4, 5, 8, 16, 32, 51, 57, 59, 83, 90, 104};
    DisplayArray(values);
    DisplayArray(valuesSorted);

    _loopCounter = 0;
    int index;
    index = IndexOf(1, values);
    System.out.println("1 is at values location " + index);
    System.out.println(_loopCounter + " comparisons were made.")

    _loopCounter = 0;
    index = IndexOf(120, values);
    System.out.println("120 is at values location " + index);
    System.out.println(_loopCounter + " comparisons were made.")

    _loopCounter = 0;
    index = BinaryIndexOf(104, valuesSorted);
    System.out.println("104 is at values Sorted location " + index);
    System.out.println(_loopCounter + " comparisons were made.")

    _loopCounter = 0;
    index = BinaryIndexOf(90, valuesSorted);
    System.out.println("90 is at values Sorted location " + index);
    System.out.println(_loopCounter + " comparisons were made.")       
}


public static int IndexOf(int value, int[] array)
{
    for (int i=0; i < array.length; i++)
    {
        _loopCounter++;
        if(array[i] == value)
            return i;
    }
    return -1;
}
    public static int BinaryIndexOf(int value, int [] array)
    {
    int start = 0;
    int end = array.length -1;
    int middle;

    while (end >= start)
    {
        _loopCounter++;
        middle = (start + end ) /2;
        if (array[middle]== value)
            return middle;
        if (array[middle]< value)
            start = middle + 1;
        else 
            end = middle - 1;
    }
    return -1;
}

public static void DisplayArray(int[] array)
{  
    for (int a : array)
    {
        System.out.print(a + " ");
    }
    System.out.println();
}

私はこのコードをテストしませんでしたが、あなたが望むように動作するようにそれを変更できるに違いありません。

于 2012-11-12T02:03:29.170 に答える