查找循环数组中任意两个索引之间的中间索引

Question

我有一个数组和三个索引：

var arr = ['a', 'b', 'c', 'd'];
var f = 0; // first element
var l = arr.length - 1; // last element
var c = 0; // current element

我正在尝试编写一个函数，使索引c在数组中循环。要求是它永远不会到达索引l 。因此，每当c达到一定值时，f和l也需要增加。

我认为

作为 c 极限的合理值是 f 和 l 之间的中间点。我写的函数是这样的：

var mod = function(x, m) {
    var r = x%m;
    return r<0 ? r+m : r;
}
while (true) {
    console.log('f', f, 'l', l, 'c', c);
    if (c == l) {
       console.log('error');
    }
    c = mod(c + 1, arr.length);
   if (c > mod(l - f, arr.length) / 2) {
      f = mod(f + 1, arr.length);
      l = mod(l + 1, arr.length);
   }
}

显然，它不起作用。有没有一个很好的简单公式来使用模运算符来获得我想要的东西，或者该方法完全错误？

这里有一个小提琴可以尝试一下：https://jsfiddle.net/wku37h9e/2/

编辑：解释这样做的目的会有点长。假设数组中存储了外部元素的位置，我必须不断移动这些元素。当c接近l时，我推进所有索引。图形上是这样的：

1. [f|c] [   ] [   ] [ l ]
2. [ f ] [ c ] [   ] [ l ]
3. [ l ] [ f ] [ c ] [   ] // here I start moving things around
4. [   ] [ l ] [ f ] [ c ]
5. [ c ] [   ] [ l ] [ f ]
6. [ f ] [ c ] [   ] [ l ]

等等。数组中的元素越多，索引之间的距离就越远。

我还使用与普通版本不同的 mod 来考虑负数。

我希望现在更清楚一点

Answer 1

我认为作为c限制的合理值是f和l之间的中间点

在 mod len 中查找两个值 low 和 high 之间的平均平均值

function midPoint(low, high, len) {
    var mid;
    low %= len;
    high %= len;
    while (low < 0) low += len; // these two lines are the
    while (high < low) high += len; // most important for direction
    mid = (low + high) / 2; // mean average
    mid %= len; // convert back to our mod
    return mid;
}

所以有

// works as expected beyond range of mod
midPoint( 1, -1, 9); // middle of 1..8 (mod 9) = 4.5
midPoint(-7,  5, 9); // middle of 2..5 (mod 9) = 3.5
midPoint(-6, 12, 9); // middle of 3..3 (mod 9) = 3
// and
midPoint( 2,  5, 9); // middle of 2..5 (mod 9) = 3.5
midPoint( 5,  2, 9); // middle of 5..2 (mod 9) = 8 (we went the other way around)

---

在整个计算之前，您实际上不必强制使用 mod，所以如果您真的想要，您可以执行以下操作，但您会在循环中失去方向

function midPoint(A, B, len) {
    var mid;
    mid = (A + B) / 2; // mean average
    mid %= len; // convert back to our mod
    while (mid < 0) mid += len; // always positive
    return mid;
}

但是，请注意此处

midPoint(-6, 3, 9); // middle of 3..3 (mod 9) = 7.5
midPoint( 3, 3 + 0 * 9, 9); // middle of 3..3 (mod 9) = 3
midPoint( 3, 3 + 1 * 9, 9); // middle of 3..3 (mod 9) = 7.5
midPoint( 3, 3 + 2 * 9, 9); // middle of 3..3 (mod 9) = 3

即3..3的中点(mod 9(既3又7.5，这是真的，但是我们现在走哪条路取决于k(B - A = k * len + a(

Answer 2

我不确定我是否理解 - 当我定义一切有效的 mod 函数时：

function test() {
    var i=0;
    var arr = ['a', 'b', 'c', 'd'];
    var f = 0; // first element
    var l = arr.length - 1; // last element
    var c = 0; // current element
    while (true && i < 1000) {
        ++i;
        console.log('f', f, 'l', l, 'c', c);
        if (c == l) {
           console.log('error');
           break;
        }
        c = mod(c + 1, arr.length);
        if (c > mod(l - f, arr.length) / 2) {
           f = mod(f + 1, arr.length);
           l = mod(l + 1, arr.length);
        }
    }
}
function mod(a,b) { return a % b;}

似乎循环 c 遍历可能的值，并且c永远不会与 l 的(连续重新计算(值相同......但我不明白你试图应用于f并在那里l

Answer 3

我只用数组长度的一半加上 c 计算l. 然后f是下一个索引。所有数字都是正数。

                            c   f   l
1. [ c ] [   ] [ l ] [ f ]  0   3   2  l = length / 2 + c, f = l + 1  both mod length
2. [ f ] [ c ] [   ] [ l ]  1   0   3
3. [ l ] [ f ] [ c ] [   ]  2   1   0
4. [   ] [ l ] [ f ] [ c ]  3   2   1
5. [ c ] [   ] [ l ] [ f ]  0   3   2
6. [ f ] [ c ] [   ] [ l ]  1   0   3

var arr = ['a', 'b', 'c', 'd'],
        c, f, l;
for (c = 0; c < arr.length; c++) {
    l = (arr.length / 2 + c) % arr.length;
    f = (l + 1) % arr.length;
    document.write('c:' + c + ' f: ' + f + ' l: ' + l + '<br>');
}