高效查找数组中两个指定ID对应元素间所有对象的方法

Great question! When dealing with large datasets (tens of thousands of items), minimizing repeated linear scans is key to performance. Your initial for-loop approach works, but it can be optimized significantly by precomputing a lookup map to avoid re-scanning the array every time you need to find indices.

The Optimized Approach #

The core idea is to build a one-time lookup map that maps each item's id directly to its index in the array. This turns O(n) index lookups into O(1) operations, which is a huge win if you're handling multiple click pairs.

Step 1: Precompute the ID-to-Index Map #

First, create a Map (or plain object, for numeric IDs) that stores each item's index using its id as the key. This only needs to run once when your data loads, or whenever the array is updated.

// Your original data
const data = [ {id: 4}, {id: 0}, {id: 3}, {id: 2}, {id: 1} ];

// Precompute the lookup map (run once)
const idToIndex = new Map(data.map((item, index) => [item.id, index]));

Step 2: Retrieve Elements Between Two IDs #

Once the map is ready, getting the elements between two clicked IDs is straightforward:

1. Look up the indices of both IDs in O(1) time.
2. Determine the start and end of your range (handling cases where the first click is after the second).
3. Slice the array to get the elements in that range.

function getElementsBetween(firstId, secondId) {
  // Get indices from the map (O(1) each)
  const idx1 = idToIndex.get(firstId);
  const idx2 = idToIndex.get(secondId);

  // Handle edge cases (IDs not found)
  if (idx1 === undefined || idx2 === undefined) {
    return [];
  }

  // Define the range (ensure start is the smaller index)
  const startIndex = Math.min(idx1, idx2);
  const endIndex = Math.max(idx1, idx2);

  // Return elements from start to end (inclusive)
  // Use slice(startIndex, endIndex) if you want strictly between elements
  return data.slice(startIndex, endIndex + 1);
}

// Example usage: user clicks id:0 and id:2
const result = getElementsBetween(0, 2);
// Result: [{id: 0}, {id: 3}, {id: 2}]

Why This Is Faster Than the For-Loop Approach #

• Initial Setup Cost: O(n) time once, which is unavoidable but only happens once.
• Query Cost: O(1) per index lookup, plus O(k) time to slice the array (where k is the number of elements in the range—this is unavoidable since you need to return those elements).
• Scalability: If you have multiple click pairs, this approach avoids re-scanning the entire array each time, which saves massive amounts of time for large datasets (e.g., 10,000 items scanned once vs. 100 times).

Trade-Offs to Consider #

• Memory Overhead: The lookup map uses O(n) additional memory, which is negligible for most use cases (even 10,000 entries take up very little space).
• Dynamic Data: If your array changes frequently (items added/removed), you'll need to update the map whenever the array changes. For example:
  • When adding an item: Push it to the array and add its ID/index to the map.
  • When removing an item: Delete it from the array, remove its entry from the map, and update the indices of all items that came after it (this is O(n) in the worst case, but if deletions are rare, it's still worth it).

Alternative for One-Time Queries #

If you only need to handle a single pair of clicks and won't reuse the indices, you can optimize the linear scan to find both indices in a single pass (instead of two separate loops):

function getElementsBetweenSinglePass(firstId, secondId) {
  let idx1, idx2;
  for (let i = 0; i < data.length; i++) {
    if (data[i].id === firstId) idx1 = i;
    if (data[i].id === secondId) idx2 = i;
    // Early exit if both indices are found
    if (idx1 !== undefined && idx2 !== undefined) break;
  }

  if (idx1 === undefined || idx2 === undefined) return [];
  
  const start = Math.min(idx1, idx2);
  const end = Math.max(idx1, idx2);
  return data.slice(start, end + 1);
}

This is better than two separate loops (O(n) time but only one pass), but still not as efficient as the lookup map approach for repeated queries.

内容的提问来源于stack exchange，提问作者Oscar Godson