Как подсчитать количество итераций в поиске методом дихотомии (бинарного поиска)?

int IndexOf(int[] Array, int Value, int Left, int Right)
        {
            int x = (Left + Right) / 2;
            if (Array[x] == Value)
            {
                return x;
            }
                if ((x == Left) || (x == Right))
                return -1;
            if (Array[x] < Value)
            {
                return IndexOf(Array, Value, x, Right);
            }
            else
            {
                return IndexOf(Array, Value, Left, x);
            }
        }

using System;
 
class Program
{
    static int counter2 = 0;
    static void Main()
    {
        int counter = 0;
        Foo(5, ref counter);
        Console.WriteLine(counter);
 
        Foo2(5);
        Console.WriteLine(counter2);
 
        Console.ReadKey();
    }
 
    static int Foo(int x, ref int counter)
    {
        counter++;
        if (x == -5)
            return 0;
        return Foo(--x, ref counter);
    }
 
    static int Foo2(int x)
    {
        counter2++;
        if (x == -5)
            return 0;
        return Foo2(--x);
    }
}