Use binary search to speed up findChildFrame()

Merge-request: 2595
Reviewed-by: mae

1 files changed, 12 insertions, 5 deletions

diff --git a/src/gui/text/qtextdocument_p.cpp b/src/gui/text/qtextdocument_p.cpp
index 2172f74..a997720 100644
--- a/src/gui/text/qtextdocument_p.cpp
+++ b/src/gui/text/qtextdocument_p.cpp
@@ -1406,11 +1406,18 @@ void QTextDocumentPrivate::changeObjectFormat(QTextObject *obj, int format)
 
 static QTextFrame *findChildFrame(QTextFrame *f, int pos)
 {
-    // ##### use binary search
-    QList<QTextFrame *> children = f->childFrames();
-    for (int i = 0; i < children.size(); ++i) {
-        QTextFrame *c = children.at(i);
-        if (pos >= c->firstPosition() && pos <= c->lastPosition())
+    /* Binary search for frame at pos */
+    const QList<QTextFrame *> children = f->childFrames();
+    int first = 0;
+    int last = children.size() - 1;
+    while (first <= last) {
+        int mid = (first + last) / 2;
+        QTextFrame *c = children.at(mid);
+        if (pos > c->lastPosition())
+            first = mid + 1;
+        else if (pos < c->firstPosition())
+            last = mid - 1;
+        else
             return c;
     }
     return 0;