Optimize QTextEngine::findItem by using a binary search.

This is basically a backport from Qt5:

- revert the revert: 22995948cd3f46780be5d8016708aeef0cd7b066
- backport from qtbase: 487583459ea7958f24cd579888a662bcce26caf3
  this fixes the off-by-one error in the binary search

Task-number: QTBUG-17209
Task-number: QTBUG-231
Change-Id: I7f62fb33cf919ecd7fb2246ae01bb23559e11bf4
Reviewed-by: Jiang Jiang <jiang.jiang@nokia.com>

1 files changed, 12 insertions, 5 deletions

diff --git a/src/gui/text/qtextengine.cpp b/src/gui/text/qtextengine.cpp
index 3af03553f6..bb453d5e28 100644
--- a/src/gui/text/qtextengine.cpp
+++ b/src/gui/text/qtextengine.cpp
@@ -1656,12 +1656,19 @@ int QTextEngine::findItem(int strPos) const
 {
     itemize();
 
-    int item;
-    for (item = layoutData->items.size()-1; item > 0; --item) {
-        if (layoutData->items[item].position <= strPos)
-            break;
+    int left = 1;
+    int right = layoutData->items.size()-1;
+    while (left <= right) {
+        int middle = ((right-left)/2)+left;
+        if (strPos > layoutData->items[middle].position)
+            left = middle+1;
+        else if (strPos < layoutData->items[middle].position)
+            right = middle-1;
+        else {
+            return middle;
+        }
     }
-    return item;
+    return right;
 }
 
 QFixed QTextEngine::width(int from, int len) const