- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Finding indexes in an ordered array
Tue, 2012-01-10, 09:43
Dear all,
I am currently looking for the most efficient algorithmic way to search an ordered array for a given double D.
The algorithm should return the index of the first element >= and of the first element =< D. For such a purpose, Arrays.binarySearch is not suitable because it returns -1 in case the element is not found.
I will be happy to hear your proposed solutions.
Best Regards
Edmondo
I am currently looking for the most efficient algorithmic way to search an ordered array for a given double D.
The algorithm should return the index of the first element >= and of the first element =< D. For such a purpose, Arrays.binarySearch is not suitable because it returns -1 in case the element is not found.
I will be happy to hear your proposed solutions.
Best Regards
Edmondo
Tue, 2012-01-10, 11:21
#2
Re: Finding indexes in an ordered array
use a binary search that doesn't discard the information when the exact element is not found. e.g.
https://github.com/Sciss/Wolkenpumpe/blob/master/src/main/scala/de/sciss...
On 10 Jan 2012, at 08:43, Edmondo Porcu wrote:
> Dear all,
> I am currently looking for the most efficient algorithmic way to search an ordered array for a given double D.
>
> The algorithm should return the index of the first element >= and of the first element =< D. For such a purpose, Arrays.binarySearch is not suitable because it returns -1 in case the element is not found.
>
> I will be happy to hear your proposed solutions.
>
> Best Regards
>
> Edmondo
>
>
>
>
>
Tue, 2012-01-10, 15:01
#3
Re: Finding indexes in an ordered array
On Tue, Jan 10, 2012 at 3:43 AM, Edmondo Porcu <edmondo.porcu@gmail.com> wrote:
The algorithm should return the index of the first element >= and of the first element =< D. For such a purpose, Arrays.binarySearch is not suitable because it returns -1 in case the element is not found.
Huh? Arrays.binarySearch returns -1-i where i is the index of the insertion point of what you're searching for. Surely you can envision how to turn this into the indices you are after.
--Rex
https://gist.github.com/1588319