c# - Binary search algorithm random generated array items not working

I have implemented binary search algorithm in a console window application in C#. I am generating random values to the array and sorting them using Random() and Array.Sort() functions respectively.

The Problem - No matter what Key(item to be searched in the array) I give, the program is returning Key not found when the array items are generated using Random function

This does not happen if I enter the array elements manually using Console.ReadLine().

TLDR: Binary Search algorithm works fine when array items are entered manually, but does not work when array items are generated using Random function.

Can anyone point out what is the mistake I am doing?

My code - Random Generated array items.

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

        Random rnd = new Random();

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

        Array.Sort(arr);

        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write("{0}\n", i);
        }

        while (true)
        {
            Console.WriteLine("Enter the number to be searched in the array.");

            var searchItem = Convert.ToInt32(Console.ReadLine());

            var foundPos = Search(arr, searchItem);

            if (foundPos > 0)
            {
                Console.WriteLine("Key {0} found at position {1}", searchItem, foundPos);
            }
            else
            {
                Console.WriteLine("Key {0} not found", searchItem);
            }
        }
    }

    public static int Search(int[] arr, int item)
    {
        var min = 0;
        var N = arr.Length;
        var max = N - 1;
        int basicOperations = 0;

        basicOperations++;
        do
        {
            var mid = (min + max)/2;

            if (arr[mid] == item)
                return mid;

            if (item < arr[mid])
                max = mid - 1; 
            else
                min = mid + 1;

            basicOperations++;
        } while (min <= max);

        return basicOperations;
    }
  }
}

Please let me know if I am doing any silly mistake or I am committing a blunder in the above code. Any help would be really helpful.