Нахождение числа бинарным поиском - вычисление максимального и минимального количества операций

Добрый день,
Хочется понять как высчитать минимальное и максимальное количество операций для нахождения произвольного числа в определенном промежутке значений. Код для примера (C#):
using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions;
namespace Rextester { public class Program { public static void Main(string[] args) { Random r = new Random(); int min = 2047; int max = 4096; int val = min; int counter = 0; int i = r.Next(2047, 4096); while(true) { Console.WriteLine("--> "+val); if(i == val) break; val = (max-min)/2 + min; if(i>val) { min = val; } else if(i
The calculated i is: "+val+", but i is: "+i+", done in "+counter+" counts.




"); } } }
В данном примере я вижу, что максимальное количество операций для нахождения числа в промежутке между 2047 и 4096 - это 11 (эмпирически, основано на 10000 запусках). Как это посчетать без запуска? Где можно почитать теоритическое обьяснение?
Спасибо!

Ответ

Так как Вы с каждой операцией отсекаете половину возможных чисел, то количество операций будет равно log(n, 2) (логарифм от n по основанию 2), где n - разница между максимом и минимумом