-3

私のアルゴリズムは、'x'(値5)がソートされた配列にあるかどうかを教えてくれると想定しています。しかし、私は0を取得し続けます。私の条件では、'x'が配列にない場合は、0が表示されます。どこが間違っているのでしょうか。

import java.util.Arrays;

public class binarySeacg {

public static void main (String[]args)
{
    int[] array = {10,7,11,5,13,8};
    exchangesort(array);
    binsearch(array,5);
    System.out.println(Arrays.toString(array));

}

public static void exchangesort(int[] S)
{
    int i,j,temp;

    for(i=0;i<S.length;i++)
        for(j=i+1;j<S.length;j++)
            if(S[i]>S[j])
            {
                temp = S[i];
                S[i] = S[j];
                S[j] = temp;
            }
}

public static int binsearch(int[] S, int x)
{
    int location, low, high, mid;

    low = 1; high = S.length;
    location = 0;

    while(low<=high && location==0)
    {
        mid =(low + high)/2;
        if(x== S[mid])
            location = mid;
        else if(x < S[mid])
            high = mid -1;
        else
            low = mid + 1;
    }
    System.out.println(location);
    return location;
}
}
4

4 に答える 4

2

を設定low = 1;すると、5が最小要素になります(つまり、インデックス0にあります)。したがって、[1、S.length]のサブリストにはありません。

を設定low = 0;し、2番目ではなく最初の要素から開始する必要があります。(Javaのインデックスは1ではなく0から始まることに注意してください)。

(PS、この特定のケースでは、ソートされたリストでは-5がインデックス0にあるため、アルゴリズムは正しいことに注意してください)。

于 2012-12-27T12:02:55.627 に答える
1

xなぜなら、あなたはあなたが渡している3、そしてあなたのリストにある価値を見つけようとしているからです。存在しません。したがって、のような他の値に変更してから5試してください。

また、low=0の代わりに開始する必要がありlow=1ます。なぜなら、それは常に最初の要素を見逃してしまうからです。

public static int binsearch(int[] S, int x)
{
    int location, low, high, mid;

    low = 0; high = S.length;
    location = 0;

    while(low<=high && location==0)
    {
        mid =(low + high)/2;
        if(x == S[mid])
        {
            location = mid;break;
        } 
        else if (x < S[mid])
        {
            high = mid - 1;
        } else
        {
            low = mid + 1;
        }
    }
    System.out.println(location);
    return location;
}

注: 出力が異なる場合は、ここで値を変更します。これはメソッドbinsearch(array,5);から呼び出されます。main()リストにある値を変更することを忘れないでください。

于 2012-12-27T12:03:03.220 に答える
1

ここでは配列を並べ替えており、並べ替えられた配列は要素の検索に使用されます。

そして、検索が成功した場合は、以下の割り当てを行います

場所=中央; これは、一致する要素のインデックスをロケーション変数に割り当てていることを意味します。

この場合、要素5は0番目のインデックスにあります。

したがって、STDOUTでは常に0になります

于 2012-12-27T12:30:03.280 に答える
0
  1. Javaおよびほとんどの言語では、インデックスは1ではなく0から始まり、nではなくn-1で終わります。
  2. 二分探索の場合、whileループを終了するときを注意深く確認し、[low、high]または[low、high)のいずれであっても、low変数とhigh変数の意味を常に覚えておいてください。
  3. この特定の問題については、配列にr個の重複がある場合も考慮する必要があります。配列の最初の要素または誰かを返すかどうか
于 2012-12-29T05:06:57.603 に答える