二进制搜索

介绍

二进制搜索是一种分而治之搜索算法。它使用 O(log n) 时间来查找搜索空间中元素的位置，其中 n 是搜索空间的大小。

二进制搜索的工作原理是在将目标值与搜索空间的中间值进行比较后，在每次迭代时将搜索空间减半。

要使用二进制搜索，必须以某种方式对搜索空间进行排序（排序）。尽管它们不违反二进制搜索属性，但无法区分重复条目（根据比较函数进行比较的条目）。

通常，我们使用小于（<）作为比较函数。如果 a <b，它将返回 true。如果 a 不小于 b 且 b 不小于 a，则 a 和 b 相等。

示例问题

你是一名经济学家，但是非常糟糕。你的任务是找到大米的均衡价格（即供给=需求的价格）。

请记住，设定的价格越高，供应量越大，需求量越小

由于你的公司在计算市场力量方面非常有效，因此当大米的价格设定为特定价格时，你可以立即获得以米为单位的供需情况。

你的老板尽快得到均衡价格，但告诉你均衡价格可以是一个至多为 4 的正整数，并且保证在该范围内恰好是 1 个正整数解。所以在你失去它之前就开始工作吧！

你可以调用函数 getSupply(k) 和 getDemand(k)，它们将完全按照问题中的说明进行操作。

示例说明

我们的搜索空间是从 1 到 10^17。因此，线性搜索是不可行的。

然而，请注意，随着 k 的上升，getSupply(k) 增加而 getDemand(k) 减少。因此，对于任何 x > y，getSupply(x) - getDemand(x)>getSupply(y) - getDemand(y)。因此，此搜索空间是单调的，我们可以使用二进制搜索。

以下 psuedocode 演示了二进制搜索的用法：

high = 100000000000000000     <- Upper bound of search space
low = 1                       <- Lower bound of search space
while high - low > 1
    mid = (high + low) / 2    <- Take the middle value
    supply = getSupply(mid)  
    demand = getDemand(mid)
    if supply > demand        
        high = mid             <- Solution is in lower half of search space
    else if demand > supply
        low = mid              <- Solution is in upper half of search space
    else                       <- supply==demand condition
        return mid             <- Found solution

该算法在 14 时运行。这可以推广到~O(log S) 时间，其中 S 是搜索空间的大小，因为在 while 循环的每次迭代中，我们将搜索空间减半（ 从[low：high]到[low：mid]或[mid：high] ）。

用递归实现二进制搜索

int binsearch(int a[], int x, int low, int high) {
    int mid;

    if (low > high)
      return -1;

    mid = (low + high) / 2;

    if (x == a[mid]) {
        return (mid);
    } else 
    if (x < a[mid]) {
        binsearch(a, x, low, mid - 1);
    } else {
        binsearch(a, x, mid + 1, high);
    }
}