c# - 用二分查找查找数字——最大和最小操作数

Question

我想知道如何计算最大和最小操作次数以找到定义范围内的特定数字。
这里是示例代码 (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<val) {
                   max = val;
               }
               counter++;
            }
            Console.WriteLine("\n\nThe calculated i is: "+val+", but i is: "+i+", done in "+counter+" counts.\n\n\n\n\n");
        }
    }
}

我可以看到，要找到 2047 到 4096 范围内的随机数，最多需要 11 次操作(基于 10000 次运行)。
在哪里可以找到计算的理论解释？

非常感谢!

Answer 1

二分搜索的工作方式是将每次操作的搜索间隔减半。因此，如果我有 200 个数字，第一次迭代会将其减少到 100，第二次减少到 50，然后是 25、12、6、3、1，然后我们就完成了。如果你有一些数学背景，这个模式看起来会很熟悉——它是一个指数函数。特别是，由于我们处理的是二元搜索，它是以二为底的指数。

因此，如果您想知道使用给定数量的操作可以搜索多少个值， 就是 2 的幂 - 如果您只想允许 8 个操作，则最多可以有要搜索的 2^8 个值 - 256。如果您想反过来，从值的数量到(最大)操作数，您需要使用反函数 - 以二为底的对数。 4096的以二为底的对数是12。

为什么你的结果是 11？因为当 i == val 为真时，您不会增加计数器；但这只是您使用的操作定义的问题。涉及 11 次减半，因为最后的操作不进行任何减半。