4

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

Improve this question
8
  • 1
    "We have an array of sorted distinct numbers that is infinitely long." Stop right there. Leave the computer science department right now and go to the math department next door. Commented Feb 8, 2015 at 15:52
  • @MikeNakis Why ? Some computer science algorithm need to assume unbound values. Commented Feb 8, 2015 at 15:54
  • 4
    You cannot have an array of infinite length. You may speak of an endless stream of items, but not of an infinite array. And of course you cannot perform binary search on a stream, because you need to know the total number of items so that you can compute the middle, and so on and so forth. Commented Feb 8, 2015 at 15:57
  • Are the numbers sorted ? Commented Feb 8, 2015 at 16:04
  • I must have missed something, are Turing machines not part of computer science any more? Commented Feb 8, 2015 at 16:07

2 Answers 2

Reset to default
8

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

In practice you wouldn't even go to 1 in your exponential search, only to the first element that is >F. And you'd only do a binary search between that position and the previous one. Of course this doesn't affect the worst case time complexity but it could give you a better average case.
@biziclop: right. The complexity is actually O(Lg i), where i is the index of the searched element. Also, I didn't say that the binary search had to be done from the first element :) but this optimization does not improve the average case, still O(Lg n) or O(Lg i), it only spares a single test.
-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).

Improve this answer

2 Comments

The catch is that you don't know n. Try and understand Yves Daoust's answer/exponential search.
Yes. But if the values are in the interval <0,1> and sorted, and "empty" elements of the array have value 1, than you know when to stop - when you reach the first element that has vaule 1! So, still, sequential search will have complexity O(n), where n is number of elements in the array.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.