6

私は、バイナリ検索アルゴリズムを最初から作成する方法を示すチュートリアルに従っていました。ただし、「割り当てられていないローカル変数「ピボット」の使用」というエラーが表示されます。私はこの言語に不慣れで、以前はもっと単純な言語しか試していませんでした。

内部ドキュメントが不足していて、空白が使用されていることをお詫び申し上げます。

エラーは、「//」を使用してラベル付けされたコードの下部近くにあります

プログラムは次のとおりです。 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Binary_Search_2
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[10];

            Random rnd = new Random();

            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = rnd.Next(1, 10);
            }

            Array.Sort(arr);
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write("{0},", arr[i]);
            }
            int Start = 0;
            int End = arr.Length;
            int Center = Start + End / 2;

            int Pivot;

            while (arr[6] > 0)
            {
                while (arr[6] < arr[Center])
                {
                    End = Center;
                    Center = (End + Start) / 2;
                    if (Pivot == arr[Center])
                    {
                        Console.WriteLine("The Index is {0}", arr[Center]);
                    }
                    break; 
                }

                while (arr[6] > arr[Center])
                {
                    Start = Center;
                    Center = (End + Start) / 2;
                    if (Pivot == arr[Center])  //**This is where the error occurs.** 
                    {
                        Console.WriteLine("The index is {0}", arr[Center]);
                    }
                }
            }
        }
    }
}

これが本当に単純なことであるとすみませんが、直接教えてくれる人がいないので、アイデアがありません。

4

3 に答える 3

3

エラーの原因は次のとおりです。

int Pivot;

ステートメントで使用する前に、の値をPivot設定する必要があります。if

これは、コードにエラーがあることを示していますPivot''s value in an。if`ステートメントをチェックしますが、割り当てることはありません。チュートリアルを調べて、次のような行を見つけてください。

Pivot = ... // <<=== some expression here

ほとんどの場合、チュートリアルに従ったときに、この行をプログラムに入力していません。

于 2012-10-03T13:58:16.027 に答える
2

二分探索の説明：

一般的な問題は、一連の要素から特定の要素を見つけることです。二分探索は、要素を見つけるまで、または要素が存在しないことを見つけるまで、「ビジョン」を半分にカットすることによってそれを行います。現在の視界の中心を確認することで、要素が左側にあるか右側にあるかがわかりますが、そのためには、要素を並べ替える必要があります。

理論上の例（要素が存在します）：

1この要素の配列で探しているとしましょう：

0, 1, 4, 4, 6, 7, 9, 10

各ステップで、視野にマークを付けます。これは、次のように中心になります。

  • S=視野の開始
  • E=視野の終わり
  • M =視野の中央=（S + E + 1）/ 2
S           M        E
0, 1, 4, 4, 6, 7, 9, 10

Mの値は6であり、1より大きいため、1がMの左側にあることがわかります。したがって、EをM-1に設定し、Mを再計算します。

S     M  E
0, 1, 4, 4, 6, 7, 9, 10

Mの値は4になりました-まだ1より大きいので、さらに左に進みます：

   M
S  E
0, 1, 4, 4, 6, 7, 9, 10

Mの値は1になりました。これは、私たちが探していた値です。これで完了です。

理論上の例（要素は存在しません）：

5この要素の配列で探しているとしましょう：

0, 1, 4, 4, 6, 7, 9, 10

各ステップで、視野にマークを付けます。これは、次のように中心になります。

  • S=視野の開始
  • E=視野の終わり
  • M =視野の中央=（S + E + 1）/ 2
S           M        E
0, 1, 4, 4, 6, 7, 9, 10

Mの値は6であり、5より大きいため、5がMの左側にあることがわかります。したがって、EをM-1に設定し、Mを再計算します。

S     M  E
0, 1, 4, 4, 6, 7, 9, 10

Mの値は4になり、5よりも小さいため、5はMの右側にある必要があります。したがって、SをM + 1に設定し、Mを再計算します。

         S
         E
         M
0, 1, 4, 4, 6, 7, 9, 10

Mの値は4になり、5よりも小さいので、もう一度右に進む必要がありますが、おっと！S = Eは、さらにどこかに行くと、それらが交差することを意味します。つまり、すでにそこを調べているので、要素は確かに存在せず、検索は終了します。

疑似コード+説明：

arr = 0, 1, 4, 4, 6, 7, 9, 10;
wanted = 5; // Holds the value to look for
index = -1; // Will hold the index of the found value (-1 means not found)

s = 0; // Initialize S with the beginning of all array
e = arr.Length - 1; // Initialize E with the last element of the array

// As long as we don't cross ourselves
while (s <= e)
{
    // Calculate M (rounded)
    m = (s + e + 1) / 2;

    // Get the current middle value
    curr = arr[m];

    // Check to see if we found our wanted value
    if (curr == wanted)
    {
        index = m;
        break;
    }
    else if (curr < wanted)
    {
        // Wanted value is further to the right
        s = m + 1;
    }
    else
    {
        // Wanted value is further to the left
        e = m - 1;
    }
}

// Here, if index is -1, the wanted value does not exist in arr.
// Otherwise, it holds it's index.

C＃ジェネリックコード：

public int BinarySearch<T>(this ICollection<T> elements, T item) where T : IComparable
{
    // Assumes that elements is already sorted!

    var s = 0;
    var e = elements.Count - 1;

    while (s <= e)
    {
        var m = (s + e + 1) / 2;

        var cmp = elements[m].CompareTo(item);

        switch (cmp)
        {
            case -1:
                s = m + 1;
                break;
            case 1:
                e = m - 1;
                break;
            default:
                return m;
        }
    }

    return -1;
}

使用法：

int[] nums = ...;
List<double> doubles = ...;
SortedSet<People> people = ...; // People compared by ID

var i0 = nums.Sort().ToArray().BinarySearch(5);
doubles.Sort();
var i2 = doubles.BinarySearch(5.3d);
var i3 = people.BinarySearch(new People{ID = 5});
于 2012-10-03T14:34:42.150 に答える
1

宣言した後、Pivo​​t変数に値を割り当てていません。ifステートメントで評価する場合、まだ初期化されていません。

于 2012-10-03T13:59:44.837 に答える