Question 2: Question 2: We have an array of sorted distinct numbers that is infi
ID: 3801239 • Letter: Q
Question
Question 2:
Question 2:
We have an array of sorted distinct numbers that is infinitely long. The first n numbers are fractions that are greater than 0 but less than 1. All the remaining elements are “1”s, and you are not given the value of n. You need to develop an algorithm to check if a user-given fraction F occurs in that array. Analyze the time complexity of your algorithm as a function of n. (An example for n=8)
1
2
3
4
5
6
7
8
9
10
11
12
..
..
..
0
0.23
0.3
0.4
0.5
0.6
0.9
1
1
1
1
1
1
1
1
1
2
3
4
5
6
7
8
9
10
11
12
..
..
..
0
0.23
0.3
0.4
0.5
0.6
0.9
1
1
1
1
1
1
1
1
Explanation / Answer
In real life we cannot have array of infinite capacity.But you can follow the below approach
Input: array a, fraction f
output: Tells whether f is a part of array or not.
Algorithm:
1.bool search(a,f,index) {
2. if(a[l]==f)
return true
3. index=2*index
4.if(a[index] > num)
return binary_search(a,0,index,f)
5.else
return search(a,f,index)
6.End }
In the above algorithm, we start searching from the first element(index=0), because we don't the upper bound. The moment we find any element greater than the fraction, we can conclude if the fraction exists, it must be on the left side of the index as the array is sorted.Now we got the higher bound for our search, we can apply binary search for the element.In each call we are doubling the index , and if condition 4 is not satisfied ,we recursiely call search.
As we are doubling the index, we can find the higher bound in O(log(n)) time, provided the array at least fiiled with half of 1's. After that we run binary search , which takes additional O(log(n)).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.