Benchmark: Binary search in sorted 100k int array

Script Preparation code:

var set = new Set();
let max = 200000;
let min = 0;

while (set.size <= 100000){
  let n = Math.floor(Math.random() * (max - min + 1)) + min;
  set.add(n);
}
var array = Array.from(set);
array.sort((a, b) => a - b);

var num = array[29204];

function binarySearch(arr, x) {

    let min = 0;
    let max = arr.length - 1;
    let index = 0;
    let val;
 
    while (min <= max) {
        index = (min + max) >> 1;
        val = arr[index];
 
        if (x < val) {
            max = index - 1;
        }
        else if (x > val) {
            min = index + 1;
        }
        else {
            return index;
        }
    }
 
    return -1;
}

Tests:

Includes
array.includes(num)
binary
binarySearch(array, num)
Set.has()
set.has(num);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Includes
binary
Set.has()

Fastest: N/A

Slowest: N/A

Autogenerated LLM Sumamry (model llama3.2:3b, generated 11 days ago):

LLMs can make mistakes. Check important info.

**Benchmark Overview**

The provided JSON represents a JavaScript microbenchmarking test case, specifically designed to measure the performance of three different scenarios: `array.includes(num)`, `binarySearch(array, num)`, and `set.has(num)`.

**Script Preparation Code**

The script preparation code is responsible for generating a large array of random integers, sorted in ascending order. The array has approximately 100,000 elements. This code also defines the `binarySearch` function, which is used to search for a specific element within the sorted array.

**Library and Functions Used**

*   **Set**: A built-in JavaScript object that provides fast membership testing.
    *   In this benchmark, `set.has(num)` checks if an element exists in the set. This operation has an average time complexity of O(1) due to the efficient implementation of sets in modern browsers.
*   **Array**: A built-in JavaScript object that provides indexing and manipulation capabilities.
    *   The `array.includes(num)` function checks if a specific element exists within the array using binary search. However, it's worth noting that the browser might not use an optimal implementation for this particular benchmark.
*   **Binary Search Function**: This custom function is used to search for an element within a sorted array. It has a time complexity of O(log n), making it relatively efficient.

**Options Compared**

The three options being compared are:

1.  `array.includes(num)`
2.  `binarySearch(array, num)`
3.  `set.has(num)`

**Pros and Cons of Each Approach:**

*   **`array.includes(num)`**:
    *   Pros: This method is widely supported across different browsers.
    *   Cons: The browser's implementation might not be optimized for this particular benchmark, leading to potential performance issues.

```
    function includes(array, x) {
      let left = 0;
      let right = array.length - 1;

while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (array[mid] === x) return true;
        if (array[mid] < x) left = mid + 1;
        else right = mid - 1;
      }
      return false;
    }

// Usage:
    array.includes(num)
  ```
*   **`binarySearch(array, num)`**:
    *   Pros: This method has a fixed time complexity of O(log n), making it relatively efficient.
    *   Cons: It requires manual implementation and might not be as widely supported across different browsers.

```
    function binarySearch(arr, x) {
      let min = 0;
      let max = arr.length - 1;

while (min <= max) {
        const mid = Math.floor((min + max) / 2);
        if (arr[mid] === x) return mid;
        if (arr[mid] < x) min = mid + 1;
        else max = mid - 1;
      }
      return -1;
    }

// Usage:
    binarySearch(array, num)
  ```
*   **`set.has(num)`**:
    *   Pros: This method has an average time complexity of O(1) due to the efficient implementation of sets in modern browsers.
    *   Cons: It might not be as widely supported across different browsers.

```javascript
    // Usage:
    set.has(num)
    ```

**Special JS Features and Syntax**

This benchmark does not use any special JavaScript features or syntax. However, it is worth noting that the `Set` object is a relatively modern feature introduced in ECMAScript 2015 (ES6).

**Alternatives**

Other alternatives to these options might include:

*   **Using a library like Fast.js or Lodash**, which provide optimized implementations for common data structures and algorithms.
*   **Implementing custom binary search algorithms** using techniques like radix sort or interpolation search, which can be more efficient than the standard binary search approach.

Keep in mind that the performance of these alternatives would depend on the specific use case and requirements.

Latest run results:

Run details: (Test run date: 4 months ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/126.0.0.0 Safari/537.36

Browser/OS: Chrome 126 on Windows

View result in a separate tab

Test name	Executions per second
Includes	45789.2 Ops/sec
binary	9799881.0 Ops/sec
Set.has()	15361550.0 Ops/sec

Related benchmarks:

Binary search in sorted 100k int array (version: 0)

Comparing performance of: Includes vs binary vs Set.has()

Created: 5 months ago by: Guest

Jump to the latest result

Includes

binary

Set.has()

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Sumamry (model llama3.2:3b, generated 11 days ago):