6

我正在学习如何从头开始创建二进制搜索算法的教程。但是我收到错误“使用未分配的局部变量'Pivot'”。我是该语言的新手，以前只尝试过更简单的语言。

对于缺乏内部文档和令人震惊的空白使用，我深表歉意。

错误位于使用“//”标记的代码底部附近

这是程序： 

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

声明后，您没有为 Pivot 变量分配任何值。在 if 语句中对其进行评估时，它仍未初始化。

于 2012-10-03T13:59:44.837 回答