Toggle navigation
MeasureThat.net
Create a benchmark
Tools
Feedback
FAQ
Register
Log In
Insert into sorted
(version: 0)
Comparing performance of:
binary search vs linear search
Created:
5 years ago
by:
Guest
Jump to the latest result
Script Preparation code:
var array = [1, 2, 3, 4, 5, 7, 8]; var value = 6;
Tests:
binary search
function sortedIndex(array, value) { var low = 0, high = array.length; while (low < high) { var mid = (low + high) >>> 1; if (array[mid] < value) low = mid + 1; else high = mid; } return low; }
linear search
function sortedIndex(array, value) { for(var i=0; i<array.length; ++i) { if(value < array[i]) return i; } return array.length; }
Rendered benchmark preparation results:
Suite status:
<idle, ready to run>
Run tests (2)
Previous results
Fork
Test case name
Result
binary search
linear 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):
I'd be happy to help you understand the provided benchmark. **What is tested on the provided JSON?** The test case compares two approaches to find the index of a value in a sorted array: binary search and linear search. **Options compared:** 1. **Binary Search**: This algorithm works by repeatedly dividing the search interval in half. If the value is less than the middle element, the algorithm repeats on the left half; otherwise, it repeats on the right half. 2. **Linear Search**: This algorithm works by checking each element in the array one by one until the target value is found. **Pros and Cons:** * **Binary Search**: + Pros: Fast for large arrays (average-case time complexity of O(log n)). + Cons: Requires the array to be sorted, which may require additional processing time. * **Linear Search**: + Pros: Simple to implement and does not require sorting the array. + Cons: Slow for large arrays (time complexity of O(n)). **Library usage:** None of the provided benchmark scripts use any external libraries. The `>>>` operator is a bitwise right shift operator, which is native to JavaScript. **Special JS features or syntax:** None mentioned in this specific benchmark. **Other considerations:** When choosing between binary search and linear search, consider the following factors: * The size of the array: Binary search is faster for large arrays, while linear search may be faster for small arrays. * The need for sorted data: If you need to perform multiple searches on the same array, sorting it first may be more efficient than using a different algorithm. **Alternative approaches:** Other algorithms that can be used to find an index in an array include: * **Hash table-based search**: This approach uses a hash table to store the array elements and their indices. It is generally faster than linear search but requires additional memory. * **Interpolation search**: This algorithm is similar to binary search but uses interpolation to estimate the position of the target value. Overall, the benchmark provides a simple way to compare the performance of two common algorithms for finding an index in a sorted array: binary search and linear search.
Related benchmarks:
non-unique-elements
Array Sorting Methods
insert and sort
unique elements in array using filter - large array
Comments
Confirm delete:
Do you really want to delete benchmark?