Question 386739 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to iterate the sequence of pulling array items from middle (eg:[0,1,2,3,4,5,6,7] -> 4 3 5 2 6 1 7 0) without generating the sequence number array?

For example, when pulling items from the middle of the array : [0,1,2,3,4,5,6,7] (length is 8)

const arr=[0,1,2,3,4,5,6,7];
while(arr.length>0){
  document.write(arr.splice(arr.length/2,1)+" ");
}

the order of index of items that would pull is : 4 3 5 2 6 1 7 0

But now I want to iterate the index but not modifying the original array and without generating the sequence array (mainly due to the original array is a bit large in real code,also want an simpler algorithm), how can I iterate it with for loop only? I tried: (c=8)

for(let i=0,c=8,half=Math.floor(c/2);i<c;i++){
    document.write(half+Math.floor(i/2)+(i%2==0?1:-1)+" ");
}

which the output is 5 3 6 4 7 5 8 6 instead of 4 3 5 2 6 1 7 0, which is not working.

Tags:

6

Answers


  1. 0

    You can see how it works right. You are basically finding the middle element and then going towards the beginning of the array or the end. Earlier you could do it, because the array length was shortening but now you do not have that luxury. So you have to simulate that.

    You can have a direction flag, which tells the pointer where to go.
    You can have a step variable, which tells how many steps to take from the center.

    Since we have to handle for both odd and even length lists, there is another variable which indicates the originalDirection we had started going out with.

    const arr= [0,1,2,3,4,5,6];
let count = arr.length;
let step = 0;
let ogDir = arr.length % 2 ? -1 : 1;
let dir = ogDir;


while(count>0){
  count--;
  document.write(arr[Math.floor(arr.length/2) + (step * dir)]+" ");
  dir*=-1; //flip the direction
  if(dir === (-ogDir) || step === 0){
    step+=1; //increase the length after every alternate iteration
  }
}

    The above does exactly what you want without altering the array.

    Login or Signup to reply.
  2. 0

    With i starting at 0, the corresponding sequence of Math.floor(i/2) values starts with 0, 0. You want only one 0 at the start, which you can achieve by using Math.ceil instead, for example:

    for(let i=0,c=8,half=Math.floor(c/2);i<c;i++){
    document.write(half+Math.ceil(i/2)*(i%2==0?1:-1)+" ");
}

    That said, do you also care about odd numbers of elements? Because that requires reversing direction:

    const arr=[0,1,2,3,4,5,6,7,8];
while(arr.length>0){
  document.write(arr.splice(arr.length/2,1)+" ");
}

document.write("<br>");

for(let i=0,c=9,half=Math.floor(c/2);i<c;i++){
    document.write(half+Math.ceil(i/2)*(i%2==0?-1:1)+" ");
    // ----------------------------------------^^^^
}

    So, in general,

    function* middleOut(n) {
    let half = Math.floor(n / 2);
    let sign = n % 2 === 0 ? 1 : -1;

    for (let i = 0; i < n; i++) {
        yield half + sign * Math.ceil(i / 2);
        sign = -sign;
    }
}

console.log([...middleOut(8)].join(' '));
    Login or Signup to reply.
  3. 0

    Find middle point by calling Math.ceil(arr.length / 2);.

    Start a loop from 0 and up to this point and either add or subtract as you go along.

    On the first run where your loop value is 0, skip the second value output

    // Run Test, expecting: 4, 3, 5, 2, 6, 1, 7, 0
const arr = [0, 1, 2, 3, 4, 5, 6, 7];
const half = Math.ceil(arr.length / 2);
for (let i = 0; i <= half; i++) {
  console.log(half - i);
  if (i == 0 || half + i == arr.length) continue; // Skip first min where i is 0. Also skip if we are at the end of an uneven array
  console.log(half + i);
}
    Login or Signup to reply.
  4. 0

    You can achieve this by directly calculating the indices you want to access using a loop:

    const arr = [0, 1, 2, 3, 4, 5, 6, 7];
const length = arr.length;
const middleIndex = Math.floor(length / 2);
for (let i = 0; i < length; i++) {
    let index;
    if (i % 2 === 0) {
        index = middleIndex - Math.floor(i / 2);
    } else {
        index = middleIndex + Math.ceil(i / 2);
    }
    document.write(arr[index] + " ");
}
    Login or Signup to reply.
  5. 0

    without generating the sequence array

    That is an ideal job for a generator function. Side note: don’t use document.write.

    function* iterInsideOut(n) {
    if (n % 2) yield n >> 1; // When odd, yield the center value
    for (let i = n >> 1; i > 0; i--) { // Yield all other values in pairs
        yield i - 1;
        yield n - i;
    }
}

const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90];

for (let i of iterInsideOut(arr.length)) {
    console.log(`arr[${i}] == ${arr[i]}`);
}
    Login or Signup to reply.
  6. 0

    Strange, but nobody offered to use just 2 indices:

    const arr = [0,1,2,3,4,5,6,7];

function iterate(arr, cb){
  let i = arr.length/2|0, j = i - 1;
  for(;j >= 0; i++, j--) {
    cb(arr[i]), cb(arr[j]);
  }
  i < arr.length && cb(i);
}

iterate(arr, i => console.log(i));

    And don’t use generators with big arrays, they are notoriously slower than usual loops.

    And a benchmark:

    ` Chrome/124
---------------------------------------------------------------------------------------
>                 n=8        |       n=80        |       n=800       |      n=8000     
Alexander   ■ 1.00x x10m 187 | ■ 1.00x   x1m 159 | ■ 1.00x x100k 143 | ■ 1.00x x10k 209
Ry            9.20x  x1m 172 |   7.17x x100k 114 |   7.83x  x10k 112 |   6.41x  x1k 134
---------------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `

    const $chunk = [0,1,2,3,4,5,6,7];
const $input = [], arr = $input;

// @benchmark Alexander
function iterate(arr, cb){
  let i = arr.length/2|0, j = i - 1;
  for(;j >= 0; i++, j--) {
    cb(arr[i]), cb(arr[j]);
  }
  i < arr.length && cb(i);
}
//@run
const result = [];
iterate(arr, i => result.push(i));
result;

// @benchmark Ry
{
function* middleOut(n) {
    let half = Math.floor(n / 2);
    let sign = n % 2 === 0 ? 1 : -1;

    for (let i = 0; i < n; i++) {
        yield half + sign * Math.ceil(i / 2);
        sign = -sign;
    }
}
// @run
const result = [];
for (let i of middleOut(arr.length)) {
    result.push(arr[i]);
}
result;
}

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search