diff options
author | Ichoran <ichoran@gmail.com> | 2014-06-26 18:17:15 -0700 |
---|---|---|
committer | Ichoran <ichoran@gmail.com> | 2014-06-26 18:17:15 -0700 |
commit | 400f28de89c27618176c6d4c55df6d50b3dcbefa (patch) | |
tree | 6c63def8467907f624b7ea71df9777a95fb3f00c | |
parent | 0a67b3c75c10b1d5e6388b10797d4aa893655e5d (diff) | |
parent | 4826d71f9f0a55c3e88847a2ae495db0f785e104 (diff) | |
download | scala-400f28de89c27618176c6d4c55df6d50b3dcbefa.tar.gz scala-400f28de89c27618176c6d4c55df6d50b3dcbefa.tar.bz2 scala-400f28de89c27618176c6d4c55df6d50b3dcbefa.zip |
Merge pull request #3758 from gourlaysama/wip/t7372
SI-7372 fix wrong insertion point for binary & linear search.
-rw-r--r-- | src/library/scala/collection/Searching.scala | 12 | ||||
-rw-r--r-- | test/files/run/search.check | 4 |
2 files changed, 8 insertions, 8 deletions
diff --git a/src/library/scala/collection/Searching.scala b/src/library/scala/collection/Searching.scala index fec4bbf502..b68124b3f8 100644 --- a/src/library/scala/collection/Searching.scala +++ b/src/library/scala/collection/Searching.scala @@ -54,7 +54,7 @@ object Searching { */ final def search[B >: A](elem: B)(implicit ord: Ordering[B]): SearchResult = coll match { - case _: IndexedSeq[A] => binarySearch(elem, -1, coll.length)(ord) + case _: IndexedSeq[A] => binarySearch(elem, 0, coll.length)(ord) case _ => linearSearch(coll.view, elem, 0)(ord) } @@ -81,18 +81,18 @@ object Searching { final def search[B >: A](elem: B, from: Int, to: Int) (implicit ord: Ordering[B]): SearchResult = coll match { - case _: IndexedSeq[A] => binarySearch(elem, from-1, to)(ord) + case _: IndexedSeq[A] => binarySearch(elem, from, to)(ord) case _ => linearSearch(coll.view(from, to), elem, from)(ord) } @tailrec private def binarySearch[B >: A](elem: B, from: Int, to: Int) (implicit ord: Ordering[B]): SearchResult = { - if ((to-from) == 1) InsertionPoint(from) else { - val idx = from+(to-from)/2 + if (to == from) InsertionPoint(from) else { + val idx = from+(to-from-1)/2 math.signum(ord.compare(elem, coll(idx))) match { case -1 => binarySearch(elem, from, idx)(ord) - case 1 => binarySearch(elem, idx, to)(ord) + case 1 => binarySearch(elem, idx + 1, to)(ord) case _ => Found(idx) } } @@ -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) |