Binary search algorithm turns up error - Use of unassigned local variable

Question

I was following a tutorial showing how to create a Binary search algorithm from scratch. However I recieve the error "Use of unassigned local variable 'Pivot'". I'm new to the language and have only tried much simpler languages previously.

I apologise for the lack of internal documentation and appauling use of white space.

The error is near the bottom of the code labled using "//"

Here is the program:

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]);
                    }
                }
            }
        }
    }
}

I'm sorry if this is actually something really simple but I don't have anyone to teach me directly and I'm out of ideas.

Answer 1

The error is caused by this line:

int Pivot;

The value of Pivot needs to be set before using it in an if statement.

This indicates an error in your code: you check Pivot''s value in anif` statement, but you never assign to it. Look through the tutorial to find a line that looks like this:

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

Most likely, you did not enter this line into your program when you followed the tutorial.

Answer 2

Binary Search explained:

The general problem is simply finding a specific element in a bunch of elements. Binary search does that by cutting "vision" in halves until finding the element, or finding out that it does not exist. By checking the center of the current view of vision, you can tell if the element is on the left or the right, but for that, the elements must be sorted.

Example in theory (element exists):

Lets say we are looking for 1 in this array of elements:

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

In each step, we mark our vision field, and it's center like so:

• S = start of vision field
• E = end of vision field
• M = middle of vision field = (S + E + 1) / 2

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

Value in M is 6, which is bigger than 1, so we know that the 1 is on M's left. Therefore, we set E to be M-1 and recalculate M:

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

Value in M is now 4 - still bigger than 1, so we go further left:

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

Value in M is now 1, which is the value we were looking for, so we're done!

Example in theory (element does not exists):

Lets say we are looking for 5 in this array of elements:

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

In each step, we mark our vision field, and it's center like so:

• S = start of vision field
• E = end of vision field
• M = middle of vision field = (S + E + 1) / 2

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

Value in M is 6, which is bigger than 5, so we know that the 5 is on M's left. Therefore, we set E to be M-1 and recalculate M:

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

Value in M is now 4, which is smaller than 5, so we know that the 5 must be on M's right. Therefore, we set S to be M+1 and recalculate M:

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

Value in M is now 4, which is smaller than 5, so we should go further right again, but oops! S=E means that if we go any where furthermore, they will cross each other, meaning we've already looked there, so the element surely does not exist, and the search is terminated.

Psuedo Code + explanations:

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# generic code:

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;
}

Usage:

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});

Answer 3

You are not assigning any value to the Pivot variable after declaring it. When evaluating it in the if statement it is still not initialized.