Benchmark: find index range in array111

Script Preparation code:

function randomIntFromInterval(min, max) {
  // min and max included
  return Math.floor(Math.random() * (max - min + 1) + min);
}
var rows = [];
let lasth = 0;
for (let i = 0; i < 10000; i++) {
  lasth += randomIntFromInterval(16, 50);
  rows.push(lasth);
}

function sliceRange(arr, min, max) {
  var l = 0,
    r = arr.length;
    while (l < r) {
      var m = ~~(l + (r - l) / 2);
      if (arr[m] < min) l = m + 1;
      else if (arr[m] > max) r = m;
      else break;
    }
    
  var lr = m,
    rl = m;
  while (l < lr) {
    m = ~~(l + (lr - l) / 2);
    if (arr[m] < min) l = m + 1;
    else lr = m;
  }
  while (rl < r) {
    m = ~~(rl + (r - rl) / 2);
    if (arr[m] > max) r = m;
    else rl = m + 1;
  }
  return [l-1, r+1];
}

Tests:

sliceRange
sliceRange(rows, 70000, 70400)
findIndex
rows.findIndex( x => x > 70000)-1

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
sliceRange
findIndex

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

**Benchmark Overview**

The provided JSON represents two test cases for measuring the performance of JavaScript in finding an index range within an array.

**First Test Case: `sliceRange`**

The first test case, "sliceRange", is designed to measure the performance of the `sliceRange` function, which takes an array and returns the indices of the subarray that falls within a specified range. The array is generated with 10,000 elements, each incremented by a random value between 16 and 50.

**Comparison Options**

The `sliceRange` function uses three approaches to find the index range:

1. **Binary Search (left)**: Finds the left boundary of the range by performing a binary search on the array from one end.
2. **Binary Search (right)**: Finds the right boundary of the range by performing a binary search on the array from the other end.
3. **Linear Search**: Iterates through the array to find the first element that exceeds the minimum value and the last element that is less than or equal to the maximum value.

**Pros and Cons**

* **Binary Search (left)**: Pros:
	+ Fastest approach, with a time complexity of O(log n).
	+ Only requires accessing the array at most twice.
*   Cons:
    * Requires the array to be sorted in ascending order, which may not always be the case.
*   Binary Search (right): Pros:
    * Similar to binary search (left), but starts from the other end of the array.
    * Still has a time complexity of O(log n).
*   Cons:
	+ Also requires the array to be sorted in ascending order, which may not always be the case.
*   Linear Search: Pros:
	+ Simple and easy to implement.
	+ Does not require any sorting or indexing of the array.
*   Cons:
    * Has a time complexity of O(n), making it slower for large arrays.
    + Requires accessing the entire array, which can lead to higher memory usage.

**Second Test Case: `findIndex`**

The second test case, "findIndex", is designed to measure the performance of the `findIndex` function, which returns the index of the first element in an array that satisfies a given condition.

**Comparison Options**

In this test case, the same three approaches are used as in the first test case: Binary Search (left), Binary Search (right), and Linear Search.

**Pros and Cons**

The pros and cons for each approach are similar to those mentioned earlier.

**Library and Special JS Features**

Neither of these test cases uses any libraries or special JavaScript features. The `sliceRange` function is a custom implementation, while the `findIndex` function is part of the JavaScript standard library.

**Alternatives**

Other alternatives for finding an index range within an array include:

*   Using a more advanced binary search algorithm that can handle unsorted arrays or arrays with duplicate elements.
*   Using a data structure such as a balanced binary search tree to store the array, which would allow for faster search times.
*   Using a library such as Lodash, which provides a `findIndex` function and other utility functions for working with arrays.

In terms of programming languages, alternatives for finding an index range within an array include:

*   Python: The `bisect` module can be used to find the insertion point for a given value in a sorted list.
*   Java: The `Arrays.binarySearch` method can be used to find the index of a given element in a sorted array.
*   C++: The `std::lower_bound` and `std::upper_bound` functions from the `<algorithm>` library can be used to find the indices of a given range within an array.

Related benchmarks:

find index range in array111 (version: 0)

Comparing performance of: sliceRange vs findIndex

Created: 4 years ago by: Guest

Jump to the latest result

sliceRange

findIndex

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):