Searching with a lie using only comparison questions

S.M. Ulam (Adventures of Mathematician Scribner, New York, 1976) presented the following problem. If one person picks a number from one to one million and the other person could ask yes or no questions, how many questions would be required to find the number with certainty if the opponent were allowed to lie once or twice. J. Spencer (Mathematics Magazine vol.57, no.2, 1984) found that by using a weight balancing strategy, if n⩽5/8*2^k/(k+1) and there is only one lie, then a number in an interval of length n can be found with at most k questions. This still means either 25 or 26 questions will be needed when n=1,000,000 and only questions of the form `Is x>c ´ are allowed. However, it will be shown that, by using a somewhat modified algorithm, if n⩽27/128*2^k/(k+1), then the number can be found in k-2 questions, no matter what the number or when the lie was told. This result means that the answer to Ulam´s question, when only 1 lie is used and only comparison questions are allowed, is, in fact, twenty-five