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

#c_sharp #алгоритм

Добрый день,

Хочется понять как высчитать минимальное и максимальное количество операций для нахождения
произвольного числа в определенном промежутке значений.
Код для примера (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

Ответы
Ответ 1

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