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

1 files 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