Index: src/btree.c
==================================================================
--- src/btree.c
+++ src/btree.c
@@ -4693,10 +4693,12 @@
     upr = pPage->nCell-1;
     assert( biasRight==0 || biasRight==1 );
     idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
     pCur->aiIdx[pCur->iPage] = (u16)idx;
     if( xRecordCompare==0 ){
+      u8 bits = 0;
+      i64 iLwr = 0, iUpr = 0;
       for(;;){
         i64 nCellKey;
         pCell = findCell(pPage, idx) + pPage->childPtrSize;
         if( pPage->intKeyLeaf ){
           while( 0x80 <= *(pCell++) ){
@@ -4705,13 +4707,17 @@
         }
         getVarint(pCell, (u64*)&nCellKey);
         if( nCellKey<intKey ){
           lwr = idx+1;
           if( lwr>upr ){ c = -1; break; }
+          iLwr = nCellKey;
+          bits |= 1;
         }else if( nCellKey>intKey ){
           upr = idx-1;
           if( lwr>upr ){ c = +1; break; }
+          iUpr = nCellKey;
+          bits |= 2;
         }else{
           assert( nCellKey==intKey );
           pCur->curFlags |= BTCF_ValidNKey;
           pCur->info.nKey = nCellKey;
           pCur->aiIdx[pCur->iPage] = (u16)idx;
@@ -4722,12 +4728,21 @@
             *pRes = 0;
             rc = SQLITE_OK;
             goto moveto_finish;
           }
         }
-        assert( lwr+upr>=0 );
-        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2; */
+        assert( lwr>=0 && upr>=lwr );
+        if( bits<3 || upr<=lwr+2 ){
+          idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2; */
+        }else if( (iUpr - iLwr)>100000 ){
+          i64 spacing = (iUpr-iLwr)/(upr-lwr);
+          idx = (intKey-iLwr)/spacing+lwr;
+          assert( idx>=lwr && idx<=upr );
+        }else{
+          idx = (intKey-iLwr)*(upr-lwr)/(iUpr-iLwr)+lwr;
+          assert( idx>=lwr && idx<=upr );
+        }
       }
     }else{
       for(;;){
         int nCell;
         pCell = findCell(pPage, idx) + pPage->childPtrSize;