You are given an innite array a[] in which the rst n cells contain integers in sorted order and the rest of the cells are lled with1. You are not given the value of n. Describe an algorithm that takes an integer x as input and nds a position in the array containing x, if such a position exists, in o(log n) time
Answers
Explanation:
.Solution:This algorithm can be broken into two phases: first we find a not too large overestimaten0forn, then we run binary search on the resulting array from 1 ton0.For the first phase, begin at entry 1 and check to see if the element there is infinity or not.If not, then try 2, then 4, 8, 16, etc, doubling each time until we see an ∞ . Note that after i steps, we will land on the over estimate n 0 = 2 i . Since the previous entry was not ∞ , it follows that 2 i - 1 ≤ n < n 0 = 2 i . Thus n 0 ≤ 2 n . This first phase takes O ( log 2 n 0 ) steps, and binary search on the array from 1 to n 0 will also take O ( log 2 n 0 ) steps. Thus the total running time is O ( log 2 n 0 ). As n 0 ≤ 2 n , log 2 n 0 ≤ log n +1, so it follows that the running time is also O (log 2 n ). Note that we could have been more efficient by terminating phase 1 early if the array elements we see while incrementing become larger than the array element we are searching for. This would make the algorithm run a bit faster if we actually implemented it in some cases, depending on where the element we’re looking for it. However, this doesn’t lead to an asymptotic speed up in our worst-case runtime, and makes the algorithm a bit more cumbersome to explain and analyze. So lesson number 1: For this course (but possibly not in practice), you may as well pick the easier to explain and analyze algorithm if it has the same asymptotic run time. Usually this means trimming off the efficiency hacks that you might add if you were to ever implement these algorithms. 6. You are given an array A [1 . . . n ] of n distinct numbers. You are told the sequence of values A [1] , A [2] , . . . , A [ n ] is unimodal. That means there is an index p where the values in the array Page 5
Image of page 5