diff options
| author | Antoine Gourlay <antoine@gourlay.fr> | 2014-02-26 00:31:47 +0100 |
|---|---|---|
| committer | Antoine Gourlay <antoine@gourlay.fr> | 2014-06-04 10:28:22 +0200 |
| commit | 85a26409f23ed8df6e82e763cb4415d519c3e9f5 (patch) | |
| tree | b756e73e33469b567b50a25f60f15415072a25e5 /src/library/scala/collection/Searching.scala | |
| parent | b24e7573a17332606d9f9da49a397e02abec1b63 (diff) | |
| download | scala-85a26409f23ed8df6e82e763cb4415d519c3e9f5.tar.gz scala-85a26409f23ed8df6e82e763cb4415d519c3e9f5.tar.bz2 scala-85a26409f23ed8df6e82e763cb4415d519c3e9f5.zip | |
SI-7372 fix wrong insertion point for binary & linear search.
It should return the position the value would have if it was a part of
the sequence. Somehow even the test was wrong.
Diffstat (limited to 'src/library/scala/collection/Searching.scala')
| -rw-r--r-- | src/library/scala/collection/Searching.scala | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/src/library/scala/collection/Searching.scala b/src/library/scala/collection/Searching.scala index fec4bbf502..6a56410d4c 100644 --- a/src/library/scala/collection/Searching.scala +++ b/src/library/scala/collection/Searching.scala @@ -88,7 +88,7 @@ object Searching { @tailrec private def binarySearch[B >: A](elem: B, from: Int, to: Int) (implicit ord: Ordering[B]): SearchResult = { - if ((to-from) == 1) InsertionPoint(from) else { + if ((to-from) == 1) InsertionPoint(from + 1) else { val idx = from+(to-from)/2 math.signum(ord.compare(elem, coll(idx))) match { case -1 => binarySearch(elem, from, idx)(ord) @@ -105,7 +105,7 @@ object Searching { while (it.hasNext) { val cur = it.next() if (ord.equiv(elem, cur)) return Found(idx) - else if (ord.lt(elem, cur)) return InsertionPoint(idx-1) + else if (ord.lt(elem, cur)) return InsertionPoint(idx) idx += 1 } InsertionPoint(idx) |