6. We know we can do binary search on a sorted array A[Lm] in (log n) time. But
ID: 3890345 • Letter: 6
Question
6. We know we can do binary search on a sorted array A[Lm] in (log n) time. But what if we don't know the value n? Your task in this problem is to give (log n)-time algorithm to search such an array for a target key K, returning the index in A of K, if it exists, or else -1. (You can assume for simplicity that the values of A are all distinct.) Since you don't know A's length, a common occurrence will be falling of the end" of A, i.e., trying to access Ali] for an i greater than (the unknown value of) n. In programming doing this might return an error or throw an exception. For the purposes of this problem, it may be simpler to assume that Ai] will evaluate to "oo" when i n, i.e., a comparison between Aln +1 and other actual key (either the target K or any Alk] for 1 S k n will always say Aln +1 is larger.Explanation / Answer
If the A.length is infinite, that means we don’t know N to apply binary search.
So before finding the key we need to find bound i.e N and then apply Binary search on it
Algorithm :
1. Let low and high be the index with low pointing to the first element of A and high will point ot second element of A.
2. Compare key to be searched with A[high]
3. If Key > A[high] then low = high and high = 2*high
4. If Key < A[high] then we know the bound, so we can apply Binary Search On top of it
TimeComplexity analysis
Let the position of key is pos . So inrder to find bound we required we need O(log pos) steps Number of steps for and we know that number of elements between high and high/2 must be O(pos) . The time complexity is O(Log pos)
i.e O(log n) once the bound n is found , Inorder to find bound also we required O(Log n) steps at max, So
The time complexity is O(log n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.