Benchmark: Include vs Binary search in sorted array

Script Preparation code:

var array = []
for (var i = 0; i < 2000; i++){
array.push(Math.random())
}
var sorted = array.sort()

function binaryIndexOf(searchElement) {

 
    var minIndex = 0;
    var maxIndex = this.length - 1;
    var currentIndex;
    var currentElement;
 
    while (minIndex <= maxIndex) {
        currentIndex = (minIndex + maxIndex) / 2 | 0;
        currentElement = this[currentIndex];
 
        if (currentElement < searchElement) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > searchElement) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }
 
    return -1;
}

Tests:

Includes
sorted.includes(5)
binary
binaryIndexOf.call(sorted, 5)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Includes
binary

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/134.0.0.0 Safari/537.36

Browser/OS: Chrome 134 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Includes	1191804.1 Ops/sec
binary	60805844.0 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the benchmark definition and test cases.

**Benchmark Definition**

The provided JSON represents a JavaScript microbenchmark that tests two approaches for searching an element in a sorted array:

1. `sorted.includes(5)`: This approach uses the built-in `includes()` method of the Array prototype, which performs a linear search (from left to right) until it finds the specified element or reaches the end of the array.
2. `binaryIndexOf.call(sorted, 5)`: This approach uses the binary search algorithm implemented in the `indexOf()` method of the Array prototype. It starts with an initial guess for the index and repeatedly divides the search interval in half until it finds the target element.

**Options Compared**

The benchmark compares the performance of these two approaches:

* **Linear Search (`includes()`)**: A simple, intuitive approach that scans the array from left to right.
* **Binary Search (`binaryIndexOf()`)**: A more efficient algorithm that uses a divide-and-conquer strategy to find the target element.

**Pros and Cons**

**Linear Search (`includes()`)**
Pros:

* Easy to implement and understand
* Suitable for small arrays or arrays with unique elements

Cons:

* Has a time complexity of O(n), making it less efficient for large arrays.
* May be slower than binary search due to the overhead of function calls.

**Binary Search (`binaryIndexOf()`)**
Pros:

* Has a time complexity of O(log n), making it much faster for large arrays.
* Can be more efficient than linear search, especially when dealing with sorted arrays.

Cons:

* Requires an initial guess or pivot element, which can lead to poor performance if the array is not sorted.
* May have higher overhead due to function call and branch prediction.

**Library**

The `indexOf()` method (used in the binary search approach) is a part of the JavaScript standard library. It's implemented by the engine and optimized for performance.

**Special JS Feature or Syntax**

This benchmark doesn't use any special JavaScript features or syntax beyond what's already discussed.

**Other Considerations**

When interpreting benchmark results, it's essential to consider:

* **Array size**: The array used in this benchmark is relatively small (2000 elements). For larger arrays, binary search may exhibit significant performance gains.
* **Sorting algorithm**: This benchmark uses the built-in `sort()` method, which can have its own performance characteristics depending on the implementation and version of JavaScript being used.
* **Hardware and engine variations**: Different engines, browsers, or hardware configurations might affect the performance of these approaches.

**Alternatives**

If you're interested in exploring alternative search algorithms for sorted arrays, consider:

1. **Exponential Search**: A more efficient algorithm that uses an exponential decay to find the target element.
2. **Interpolation Search**: An algorithm that estimates the position of the target element using interpolation techniques.

Keep in mind that while these alternatives might offer better performance, they may also be more complex to implement and understand.

Related benchmarks:

Include vs Binary search in sorted array (version: 0)

Comparing performance of: Includes vs binary

Created: 9 years ago by: Guest

Jump to the latest result

Includes

binary

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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