它是一种模式确定要在二进制搜索中使用什么索引变量吗？

Question

做的时候https://leetcode.com/problems/search-insert-position。我发现很难确定索引变量的组合。

例如，我们在代码的每一层都有如下组合。

(1)
l = 0 (stable)
r = len; r = len-1; (outbound / inbound)

(2)
loop(l < r); loop(l <= r) (outbound / inbound)

(3)
l = ind+1 (stable)
r = ind; r = ind-1 (include / exclude)

所以现在你有不同的索引变量组合，其中一些是有效的，但如果你改变其中一个，它不会通过所有测试用例

combo 1:
l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work

combo 2:
l=0, r=len-1 (inbound); loop(l < r); l=ind+1, r=ind (include); !work

combo 3:
l=0, r=len (inbound); loop(l < r); l=ind+1, r=ind-1 (exclude); !work

combo 4:
l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work

combo 5:
l=0, r=len-1 (inbound); loop(l<=r); l=ind+1, r=ind (include); work

comb 6:
l=0, r=len (outbound); recursive(l<=r); l=ind+1, r=ind (include); work

下面是我试玩的代码。其中一些正在工作，其中一些不工作

// sm: l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length; // outbound
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len-1 (inbound); loop(l < r); l=ind+1, r=ind (include); !work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length - 1; // inbound, cannot insert outbound
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len (inbound); loop(l < r); l=ind+1, r=ind-1 (exclude); !work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind - 1;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len-1 (inbound); loop(l<=r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length - 1;
  let ind;

  while (l <= r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind - 1;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len (outbound); recurive(l<=r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  return recur(ns, l, r, tar);
};

var recur = function (ns, l, r, tar) {
  if (l >= r) {
    return l;
  }

  const ind = Math.floor((l + r) / 2);

  if (ns[ind] === tar) {
    return ind;
  } else if (ns[ind] < tar) {
    return recur(ns, ind + 1, r, tar);
  } else if (ns[ind] > tar) {
    return recur(ns, l, ind, tar);
  }
};

const ns = [1, 3, 5, 6];
const tar = 5;
const out = searchInsert(ns, tar);
console.log(out);

我的问题是，当您遇到二分查找问题时？您如何知道要使用哪个索引组合？因为它真的取决于问题、线索和错误

Answer 1

对于刚开始学习二分查找的人来说，这是一个很常见的问题。我将尝试逐个分析您的示例，看看您是否能更好地理解。

改写

先重新表述问题会很有帮助。如果我们设置 ns[ns.length] infinity，问题本质上是要求您找到第一个 i 使得 ns[i] >= tar.

想法

考虑数组[1, 3, 5, 6]和tar = 5，对每个元素使用上面的定义，我们可以看到数组实际上可以计算为[F, F, T, T]，所以我们需要做的只是找到第一个 T 的索引。这同样适用于任何数组。

实施

现在问题的核心来了。我将首先说明为什么组合 2 和 3 不起作用。

在组合 2 中， l=0, r=len-1 (inbound); loop(l < r); l=ind+1, r=ind (include);:
我们可以看到 r 被初始化为 len - 1。但是，如果给定的数组计算结果为 [F, F, F, F] 怎么办？答案是 4 但 r 被初始化为 3，这意味着 4 永远不会被视为答案。

在组合 3 中，l=0, r=len (inbound); loop(l < r); l=ind+1, r=ind-1 (exclude);：
我们可以看到 r=ind-1 如果 ns[ind] > tar。但是，我们想找到第一个 i 使得 ns[ind] >= tar 所以 ns[ind] 仍然是一个潜在的候选人！因此在这个阶段排除它是不正确的。

要考虑的示例是 [3, 4, 5] 和 tar = 4。在第一次迭代中，ind = 1和4立即被淘汰，这应该是正确答案。

您可以通过查看您的二分搜索是否会错误地排除潜在候选人来验证其他组合是否正常工作。

补充说明

正如您所说，使用哪个索引组合确实取决于问题。但是，在这个特定问题中，如果我被要求找到第一个 i 使得 ns[i] >= tar，我将有一个更清晰的实现如下：

var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  let ind;
  ns.push(Infinity);
  while (l < r) {
    ind = Math.floor((l + r) / 2);
    if (ns[ind] >= tar) {
      r = ind;
    } else {
      l = ind + 1;
    }
  }
  return r; // insert
};

这只是找到数组中的第一个 T。

它是一种模式确定要在二进制搜索中使用什么索引变量吗？

Is it a pattern determine what index variable to be used in binary search?

javascript

algorithm

binary-search

node.js

改写

想法

实施

补充说明