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 | |
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.
-rw-r--r-- | src/library/scala/collection/Searching.scala | 4 | ||||
-rw-r--r-- | test/files/run/search.check | 4 |
2 files changed, 4 insertions, 4 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) diff --git a/test/files/run/search.check b/test/files/run/search.check index a885696509..e0c55043e3 100644 --- a/test/files/run/search.check +++ b/test/files/run/search.check @@ -1,6 +1,6 @@ Found(2) Found(4) -InsertionPoint(9) +InsertionPoint(10) Found(2) Found(4) -InsertionPoint(9) +InsertionPoint(10) |