From e2584b9e910da18e7e472b5681eb7d0d1630647a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Pascal=20L=C3=A9tourneau?= <pascal.letourneau@gmail.com>
Date: Mon, 14 Sep 2009 16:54:13 -0400
Subject: Use qLowerBound in qBinaryFind

The current implementation of qBinaryFind use 64bit arithmetics even
on a 32bit system, which make it slow
The docs mention qBinaryFind will find any occurence of the search
value not necessarily the first one, but this is not case with
current implementation
So nothing prevents the use of qLowerBound

Reviewed-by: Olivier Goffart
Merge-request: 1513
---
 src/corelib/tools/qalgorithms.h | 42 ++++++++++-------------------------------
 1 file changed, 10 insertions(+), 32 deletions(-)

diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h
index a68ce27..f70821a 100644
--- a/src/corelib/tools/qalgorithms.h
+++ b/src/corelib/tools/qalgorithms.h
@@ -295,23 +295,12 @@ template <typename RandomAccessIterator, typename T>
 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 {
     // Implementation is duplicated from QAlgorithmsPrivate.
-    qint64 l = 0;
-    qint64 r = end - begin - 1;
-    if (r < 0)
-        return end;
-    qint64 i = (l + r + 1) / 2;
-
-    while (r != l) {
-        if (value < begin[i])
-            r = i - 1;
-        else
-            l = i;
-        i = (l + r + 1) / 2;
-    }
-    if (begin[i] < value || value < begin[i])
+    RandomAccessIterator it = qLowerBound(begin, end, value);
+
+    if (it == end || value < *it)
         return end;
-    else
-        return begin + i;
+
+    return it;
 }
 
 template <typename RandomAccessIterator, typename T, typename LessThan>
@@ -520,23 +509,12 @@ Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator
 template <typename RandomAccessIterator, typename T, typename LessThan>
 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 {
-    qint64 l = 0;
-    qint64 r = end - begin - 1;
-    if (r < 0)
-        return end;
-    qint64 i = (l + r + 1) / 2;
-
-    while (r != l) {
-        if (lessThan(value, begin[i]))
-            r = i - 1;
-        else
-            l = i;
-        i = (l + r + 1) / 2;
-    }
-    if (lessThan(begin[i], value) || lessThan(value, begin[i]))
+    RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);
+
+    if (it == end || lessThan(value, *it))
         return end;
-    else
-        return begin + i;
+
+    return it;
 }
 
 } //namespace QAlgorithmsPrivate
-- 
cgit v0.12