This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Finding indexes in an ordered array

3 replies
edmondo1984
Joined: 2011-09-14,
User offline. Last seen 28 weeks 3 days ago.
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





Ben Jackman
Joined: 2009-02-04,
User offline. Last seen 42 years 45 weeks ago.
Re: Finding indexes in an ordered array
Here is the code that we use for this:
https://gist.github.com/1588319



Sciss
Joined: 2008-12-17,
User offline. Last seen 28 weeks 5 days ago.
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
>
>
>
>
>

ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: Finding indexes in an ordered array

On Tue, Jan 10, 2012 at 3:43 AM, Edmondo Porcu <edmondo [dot] porcu [at] gmail [dot] 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

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland