Bug #73386 for ranges, innodb doubles estimates, or caps estimates to half the table

Description:
Reported by HarrisonF.

The code in btr_estimate_n_rows_in_range may cap the n_rows to half the table, 
or double the number.  This seems to be a rather arbitrary way to implement the algorithm.

Notice the testcase outputs indicated by <------

How to repeat:
drop table if exists t;
create table t (a serial) engine=innodb;
insert t values (),(),(),(),(),(),();
insert t select null from t,t a,t b,t c,t d,t e limit 100000;
optimize table t;analyze table t;

select count(*), min(a), max(a) from t;
explain select count(*) from t where a < 10;   -- estimate 
select count(*) from t where a < 10;           -- actual

explain select count(*) from t where a < 100;  -- estimate 
select count(*) from t where a < 100;          -- actual

explain select count(*) from t where a < 1000;  -- estimate 
select count(*) from t where a < 1000;          -- actual

explain select count(*) from t where a < 10000; -- estimate <------
select count(*) from t where a < 10000;         -- actual

explain select count(*) from t where a < 20000; -- estimate <------
select count(*) from t where a < 20000;         -- actual

explain select count(*) from t where a < 40000; -- estimate <------
select count(*) from t where a < 40000;         -- actual

explain select count(*) from t where a < 200000;-- estimate <-------
select count(*) from t where a < 200000;        -- actual

Suggested fix:
improve the algorithm so that arbitrary capping/doubling is not needed.

output from 5.7.5

Attachment: bug73386_5.7.5_output.txt (text/plain), 9.50 KiB.

Posted by developer:
 
Just for reference: I was able to reproduce as well in 5.1.63 , 5.5.25 , 5.5.45

Very similar (Most probably duplicate) bug #78192

https://bugs.mysql.com/bug.php?id=99998
https://bugs.mysql.com/bug.php?id=99997

This bug is the original of the following duplicate:

https://bugs.mysql.com/bug.php?id=99997