Divide and subdue algorithms (using binary search!)

Question

I'm new here. As a gradient student, I have been brainstorming on algorithms for some time. I appreciate any help that could be expanded on the issue below. I searched enough, and I could not find any close solution to this problem.

We have an array of sorted different numbers that is infinitely long. The first n numbers are fractions that are greater than 0 but less than 1. All other elements are equal to "1", and you are not assigned the value n. You need to develop an algorithm to check if there is a user-defined fraction F in this array. Analyze the time complexity of the algorithm as a function of n. (Example for n = 8, where 1 starts at the 8th position of the array)

My approach: I guess the best way to solve this is to use binary search. Every time we can reduce the size of the array by half and finally come to the found part. Suppose the array has m elements, including 1. The number of fractional elements is n. The complexity of performing a binary search over the entire array is O (log (m)). Since I am asked to express the time complexity in terms of n, m = n + k (assuming the number 1 in the array is k) Thus, the time complexity of this problem is O (log (n + k)).

Please give up your thoughts. Thanks

Answer 1

, .. m, .

, 1. O (Lg n). O (Lg n).

k .

, .. , , , , .

Answer 2

. 0 1, , , O (lg (n + k)), n k - , . , , . , , .

, , O (n).