I have an array with values and I need to find all values between min and max. I believe I need to construct some kind of search tree, is that correct? I want something like:
var values : number[] = tree.findBetween(min : number, max: number);
The performance of the search is the main criterion.
Also, I don't need to change the tree (add/remove values) once it is constructed.
What is it that I need? A binary-tree? A balanced search tree? A static search tree?
Where do I start?
Thanks to @bergi for the answer, I really do not need to construct a search tree to perform a binary search on a sorted array, so I should be able to find my values and get the part of the array between them.
Just for curiosity, I found an interesting article comparing the performance of the binary search with an ordinary search - loop through the array. The article somehow mistakenly includes the time to sort the array into the search time - you are supposed to use the binary search only if you have a sorted array (if you can pre-sort it before of the performance critical period). I run the code with up to some 1e7 items and the binary search on sorted arrays takes 0 milliseconds as compared to tens of milliseconds for simply looping the array.
In the end, this is the fastest implementation of binary search I could find. https://oli.me.uk/2014/12/17/revisiting-searching-javascript-arrays-with-a-binary-search/
Thanks for everyone's help.
Oh, sorry, my Globish sometimes plays tricks on me. Otherwise, I do not see too much where the difficulty is for such a question, but here is always a new answer (hoping that this time I will not be next to the plate)
outside this : what could it be more faster than a native js method ?
const
MaxValue = 50,
MinValue = 10
;
let
ArrayOrigin = [12, 5, 8, 130, 44, 25, 14, 42, 36 ],
ArrayInLimits = ArrayOrigin.filter( elm=> elm>MinValue && elm<MaxValue)
;
console.log( ...ArrayInLimits );
