wish_me's blog

An interesting problem on Search
By wish_me, history, 7 years ago, In English

Given an array of size N, there exist a pattern such that, a[i]-M <= a[i+1] <= a[i]+M . Suggest an algorithm to search for a number in the given array. The solution should be better than O(n).

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Are you sure it's supposed to be better than O(n) even when the array would be full of repeated 4 and 2 (I mean, 4 2 4 2 4 2 4 2 .....) and in the middle would be 3 and you had to find it?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry without repetition.Please tell your approach?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was just asking a question to make sure the algorithm is supposed to be better than O(n) even in the absolute worst case.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      M is an input to the program, right? And are there any other constraints on Array?

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what do you mean without repetition? do you mean that the numbers are distinct?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes.Please tell the approach

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          if M is small, suppose we want to find b: so we start from the first element, if the element is b, we are done. else we will jump |(a[cur]-b)/M|+1 steps. this is because we know anything in between would not be able to be equals to b. Repeat until we find b.

          The time complexity of the algorithm is proportional to the number of jumps. And we know that at worst case we can only have 2*M jumps of length 1, 2*M jumps of length 2 and so on till 2*M jumps of length x.

          So we have 2M(1+2+...+x) = N-1 as the sum of the jumps can be as most N-1. So (x+1)x = (N-1)/M, and x is about sqrt((N-1)/M), so the number of jumps is 2M*sqrt((N-1)/M) = 2*sqrt((N-1)M)

          So the time complexity is O(sqrt(N*M)), it is better than O(N) if M is < N, and if M is greater than N, the complexity is O(N) as there is still at most N jump.

          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe i misunderstood the problem, but how can we do it faster than reading array? If it is problem with Q queries, why can't we just memorize position of each value, i.e. will make map, where m[i] — position of number i and answer in O(logN) for each query. If it is correct it can be done in O((N + Q)logN) or in O(NlogN + Q). But if this task is interactive i don't know what to do.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    usually in this kind of situation, the array will be given, so can you consider the time complexity without reading the array.

    → Reply