首页 文章

二进制搜索范围

提问于
浏览 次
2

我总是遇到最艰难的时刻，而且我还没有看到对于那些被认为如此普遍和高度使用的东西的明确解释 .

我们已经知道标准的二进制搜索 . 给定起始下限和上限，找到中间点（低于更高）/ 2，然后将其与数组进行比较，然后相应地重新设置边界等 .

但是，调整搜索以查找所需的差异（对于按升序排列的列表）：

  • 最小值> =目标

  • 最小值>目标

  • 最大值<=目标

  • 最大值<目标

似乎每种情况都需要对算法进行非常小的调整，但我永远无法使它们正常工作 . 我尝试改变不等式，返回条件，我改变边界的更新方式，但似乎没有任何一致性 .

处理这四种情况的最终方法是什么？

algorithm binary-search

3 回答

  • 0

    二进制搜索（至少我实现它的方式）依赖于一个简单的属性 - 谓词对于区间的一端是成立的，而对于另一端则不成立 . 我总是认为我的间隔在一端关闭而在另一端打开 . 那么让我们来看看这段代码：

    int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in

while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (pred(a[mid])) {
    beg = mid;
  } else { 
    end = mid;
  }
}
// answer is at a[beg]

    这适用于您定义的任何比较 . 只需将 pred 替换为 <=target 或 >=target 或 <target 或 >target 即可 .

    循环退出后， a[beg] 将是给定不等式所持有的最后一个元素 .

    因此，我们假设（如评论中建议的那样）我们想要找到 a[i] <= target 的最大数字 . 然后，如果我们使用谓词 a[i] <= target ，代码将如下所示：

    int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] <= target) {
    beg = mid;
  } else { 
    end = mid;
  }
}

    循环退出后，您要搜索的索引将是 beg .

    另外，根据比较，您可能必须从数组的右端开始 . 例如 . 如果您正在搜索最大值> = target，您将执行以下某种操作：

    beg = -1;
end = n - 1;
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] >= target) {
    end = mid;
  } else { 
    beg = mid;
  }
}

    您要搜索的值将使用索引 end . 请注意，在这种情况下，我考虑间隔 (beg, end] ，因此我略微修改了起始间隔 .

    回复于
  • 0

    基本二进制搜索是搜索与目标键相等的位置/值 . 虽然它可以扩展到 find the minimal position/value which satisfy some condition ，或 find the maximal position/value which satisfy some condition .

    假设数组是升序，如果找不到满意的位置/值，则返回-1 .

    代码示例：

    // find the minimal position which satisfy some condition
  private static int getMinPosition(int[] arr, int target) {
      int l = 0, r = arr.length - 1;
      int ans = -1;
      while(l <= r) {
          int m = (l + r) >> 1;
          // feel free to replace the condition
          // here it means find the minimal position that the element not smaller than target
          if(arr[m] >= target) {
              ans = m;
              r = m - 1;
          } else {
              l = m + 1;
          }
      }
      return ans;
  }

  // find the maximal position which satisfy some condition
  private static int getMaxPosition(int[] arr, int target) {
      int l = 0, r = arr.length - 1;
      int ans = -1;
      while(l <= r) {
          int m = (l + r) >> 1;
          // feel free to replace the condition
          // here it means find the maximal position that the element less than target
          if(arr[m] < target) {
              ans = m;
              l = m + 1;
          } else {
              r = m - 1;
          }
      }
      return ans;
  }

    int[] a = {3, 5, 5, 7, 10, 15};
    System.out.println(BinarySearchTool.getMinPosition(a, 5));
    System.out.println(BinarySearchTool.getMinPosition(a, 6));
    System.out.println(BinarySearchTool.getMaxPosition(a, 8));
    回复于
  • 0

    您需要的是二进制搜索，它允许您在最后一步参与该过程 . 典型的二进制搜索将接收 (array, element) 并生成一个值（通常是索引或未找到） . 但是，如果您有一个修改后的二进制文件，它接受在搜索结束时调用的函数，则可以涵盖所有情况 .

    例如，在Javascript中使其易于测试，以下二进制搜索

    function binarySearch(array, el, fn) {
    function aux(left,  right) {
        if (left > right) {
            return fn(array, null, left, right);
        }

        var middle = Math.floor((left + right) / 2);
        var value = array[middle];

        if (value > el) {
            return aux(left, middle - 1);
        } if (value < el) {
            return aux(middle + 1, right);
        } else {
            return fn(array, middle, left, right);
        }
    }

    return aux(0, array.length - 1);
}

    允许你用特定的返回功能覆盖每个案例 .

    • 默认
      function(a, m) { return m; }

    • 最小值> =目标
      function(a, m, l, r) { return m != null ? a[m] : r + 1 >= a.length ? null : a[r + 1]; }

    • 最小值>目标
      function(a, m, l, r) { return (m || r) + 1 >= a.length ? null : a[(m || r) + 1]; }

    • 最大值<=目标
      function(a, m, l, r) { return m != null ? a[m] : l - 1 > 0 ? a[l - 1] : null; }

    • 最大值<目标
      function(a, m, l, r) { return (m || l) - 1 < 0 ? null : a[(m || l) - 1]; }

    回复于

相关问题