CODEWITHSUNDEEP
c#
maverick
maverick

Reputation: 193

Why do I get an index of -1 for C# array?

I get the following result for the code I added right after the output: 

Initializing
2.4

Searching
Index: 55504605
Time: 0.0374
Index: 21891944
Time: 0.0178
Index: 56663763
Time: 0.0425
Index: 37441319
Time: 0.0261
Index: -1
Time: 0.0676
Index: 9344095
Time: 0.0062

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new Stopwatch();
            int[] big = new int[100000000];
            Console.WriteLine("Initializing");
            sw.Start();
            var r = new Random(0);
            for (int i=0; i < big.Length; ++i)
            {
                big[i] = r.Next(big.Length);
            }
            sw.Stop();
            Console.WriteLine(sw.Elapsed.ToString("s\\.f"));
            Console.WriteLine();

            Console.WriteLine("Searching");
            for (int i=0; i<6; ++i)
            {
                int searchFor = r.Next(big.Length);
                sw.Reset();
                sw.Start();
                int index = Array.IndexOf(big, searchFor);
                sw.Stop();
                Console.WriteLine("Index: {0}", index);
                Console.WriteLine("Time: {0:s\\.ffff}", sw.Elapsed);
            }
            Console.Read();
        }
    }
}

I do not understand why I get an index of -1 for the 5th iteration. Isn't the code returning the location of the match within the array? Isn't array numbered from 0 to 100,000,000?

I am not sure if I can ask a follow up question here. The question is about array binary search implemented in the CLR of C# namespace. According to this link if the number is not found, the search returns the complement of the index of an array element. It says if the number is less than one or two elements, the result will the bit wise complement of the index of the first element which is greater. If the value is larger than all the elements, the result will be bit wise complement of the index of the last element of the array. I want to know what good is that result and what is the logic behind returning the bit wise complement of these values?

Below is my results and my modified code: 

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new Stopwatch();
            int[] big = new int[100000000];
            Console.WriteLine("Initializing");
            sw.Start();
            var r = new Random(0);
            for (int i=0; i < big.Length; ++i)
            {
                big[i] = r.Next(big.Length);
            }
            sw.Stop();
            Console.WriteLine(sw.Elapsed.ToString("s\\.f"));
            Console.WriteLine(sw.ElapsedTicks.ToString("s\\.f"));
            Console.WriteLine();

            Console.WriteLine("Searching");
            for (int i=0; i<6; ++i)
            {
                int searchFor = r.Next(big.Length);
                sw.Reset();
                sw.Start();
                int index = Array.IndexOf(big, searchFor);
                sw.Stop();
                Console.WriteLine("Index: {0}", index);
                Console.WriteLine("Time: {0:s\\.ffff}", sw.Elapsed);
            }
            Console.WriteLine();

            Console.WriteLine("Sorting");
            sw.Reset();
            sw.Start();
            Array.Sort(big);
            sw.Stop();
            Console.WriteLine(sw.Elapsed.ToString("s\\.f"));
            Console.WriteLine();

            Console.WriteLine("Searching (binary)");
            for (int i=0; i<6; ++i)
            {
                int searchFor = r.Next() % big.Length;
                sw.Reset();
                sw.Start();
                int index = Array.BinarySearch(big, searchFor);
                sw.Stop();
                Console.WriteLine("Index: {0}", index);
                Console.WriteLine("Time: {0:s\\.fffffff}", sw.Elapsed);
            }
            Console.ReadLine();
        }
    }
}



Index: 55504605
Time: 0.0460
Index: 21891944
Time: 0.0147
Index: 56663763
Time: 0.0377
Index: 37441319
Time: 0.0248
Index: -1
Time: 0.0755
Index: 9344095
Time: 0.0068

Sorting
16.5

Searching (binary)
Index: 8990721
Time: 0.0000844
Index: 4404823
Time: 0.0000046
Index: 52683151
Time: 0.0000059
Index: -37241611
Time: 0.0000238
Index: -49384544
Time: 0.0000021
Index: 88243160
Time: 0.0000064

Just a couple of qualifying statements: 1- The above code is not mine. I am just trying to understand it. 2- If I used any terms incorrectly, please let me know as I am in learning process.

Upvotes: 0

Views: 211

Answers (1)

CodeCaster
CodeCaster

Reputation: 151674

Isn't array numbered from 0 to 100,000,000?

No. You initialize an array of 100000000 items with 100000000 random numbers.

int[] big = new int[100000000];
for (int i=0; i < big.Length; ++i)
{
    big[i] = r.Next(big.Length);
}

You then try to find the index of six random numbers:

for (int i=0; i<6; ++i)
{
    int searchFor = r.Next(big.Length);
    int index = Array.IndexOf(big, searchFor);

However, there's no guarantee that the big array contains all numbers between 0 and 100000000. Random.Next() can return duplicate values, meaning some other numbers from that range are missing.

So there is a chance that r.Next(big.Length) in the second loop returns a number that isn't in the array, hence the return value of -1.

If you actually want to shuffle the numbers from 0-99999999, then instead generate a list containing those numbers, and shuffle it.

Upvotes: 10

Related Questions