Divide and Conquer Algorithms (Application of Binary Search?!)

Question

I am new here. Being a grad student, I have been brainstorming on algorithms for a while now. I appreciate any help that can be extended regarding the problem below. I have searched enough and I couldn't find any close solution to this problem.

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 , where the 1's begin at 8th position of the array)

My approach: I am guessing that the best way to solve this is by employing binary search. Each time we can bring down the size of the array by half and finally, arrive at the fraction to be found. Let us assume that there are m elements in the array, including the 1's. The number of fractional elements is n. The time complexity of performing the binary search on the whole array is O(log(m)). Since I am asked to express the time complexity in terms of n, m = n+k (assuming that the number of 1's in the array is k) So the time complexity of this problem is O(log(n+k)).

Please throw in your thoughts. Thanks

Answer 1

The binary search works for sorted arrays. If you have fractions which are between 0 and 1, your array is sorted, so you can do binary search on whole array, and it has complexity of O(lg (n+k)), where n and k are values as you stated in your question. Anyway, your array can be very big, and the number of fractions rather small. So, regardless time complexity, in this case sequential search will be faster.

So, in your case, I suggest simple sequential search, which has complexity O(n).

Answer 2

You can indeed solve that for an infinite array, i.e. not knowing m, by exponential search.

Try the first element and double the index until you get a 1. This will take O(Lg n) steps. Then you switch to binary search and get the answer in additional O(Lg n) steps.

The value of k is irrelevant.

This approach can make sense in the real world, i.e. with an array of finite but unknown size, provided that at least half of the array is filled with ones, so that the search terminates in-bounds.