Benchmark: LinearSearch vs BinarySearch

Script Preparation code:

var binarySearch = (items, comparator) => {
    let start = 0;
    let end = items.length - 1;

    while(start <= end) {
        const mid = Math.floor((start + end) / 2);
        const result = comparator(items[mid]);
        if (result === 0) return mid;
        else if (result < 0) start = mid + 1;
        else end = mid - 1;
    }

    return -1;
};

var numbers = [...Array(100_000_000)].reduce((acc, _) => {
    const prev = acc.length ? acc[acc.length - 1] : 0;
    acc.push(prev + Math.round(Math.random() * 100));
    return acc;
}, []);

var randomPosition = Math.floor(Math.random() * numbers.length);
var target = numbers[randomPosition];

Tests:

Linear Search
var index = numbers.findIndex(num => num === target);
Binary Search
var position = binarySearch(numbers, num => num - target);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Linear Search
Binary Search

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.

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

**Benchmark Definition**

The benchmark measures the performance of two search algorithms: Linear Search and Binary Search. The script preparation code defines these two functions:

* `binarySearch`: an implementation of the Binary Search algorithm, which finds the index of a target element in a sorted array.
* `numbers`: an array of 100 million random numbers generated using `Math.random()`.
* `target`: a randomly selected element from the `numbers` array.

**Html Preparation Code**

There is no HTML preparation code provided. The test cases are defined directly in the benchmark definition JSON.

**Individual Test Cases**

The benchmark consists of two test cases:

1. **Linear Search**: The `findIndex` method of the Array prototype is used to search for the `target` element in the `numbers` array.
2. **Binary Search**: The custom `binarySearch` function is used to search for the `target` element in the `numbers` array.

**Options Compared**

The benchmark compares two options:

* Linear Search (using `findIndex`)
* Binary Search (using a custom implementation)

**Pros and Cons of Each Approach**

1. **Linear Search**
	* Pros:
		+ Simple to implement
		+ Works for unsorted arrays
	* Cons:
		+ Has a worst-case time complexity of O(n), which can be slow for large datasets
2. **Binary Search**
	* Pros:
		+ Fastest search algorithm for sorted arrays (average case: O(log n))
		+ More efficient than Linear Search for large datasets
	* Cons:
		+ Requires the array to be sorted, which can be time-consuming to achieve
		+ May not work correctly if the array is unsorted or contains duplicate elements

**Library and Purpose**

In this benchmark, there is no explicit library being used. However, the `Array.prototype.findIndex` method is a part of the JavaScript standard library, which provides an efficient way to search for an element in an array.

**Special JS Features or Syntax**

There are no special JavaScript features or syntaxes being tested in this benchmark. The focus is on comparing the performance of two basic search algorithms.

**Other Alternatives**

If you wanted to test alternative search algorithms, some other options could be:

* Hash-based search (e.g., using a hash table)
* Interpolation search
* Exponential search
* Jump search

These alternatives might provide better performance for specific use cases, but they also come with their own trade-offs and considerations.

Related benchmarks:

LinearSearch vs BinarySearch (version: 0)

Comparing performance of: Linear Search vs Binary Search

Created: 3 years ago by: Guest

Jump to the latest result

Linear Search

Binary Search

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):