TRICKY :: How do I find the first element in an unsorted array, which is greater than or equal to a given value x in O(log n)?

Given a unsorted sequence of positive integers and an integer M, return the first number in the sequence which is greater than M (or -1 if it doesn’t exist).

Example: if sequence = [2, 6, 50, 9, 1], M = 7 then ans = 50

O(log n) for each query required (after preprocessing).

My initial thought is using set or AVL trees but I am not getting the answer.

UPD: Let us suppose the array can’t be sorted as N is 10^7 and O(nlogn) sorting will not work

1 Like

you can use hashing or sort the array using counting sort and apply binary search over the array or you can use treeset.

It’s quite simple…

My solution with O(N) preprocessing + O(logN) query

You just need a single observation to boil down this problem into a simple classical problem…

(if the array doesn’t change during the queries)

Here it goes…

Say, the given array is {5,4,3,8,9}

So, By trying various values of M, you can see, the output will never be 4 or 3, because a greater element (5) is already present to the left of both of these elements…

So, it doesn’t matter if you even store these elements.

You simply store the array {5, 8, 9}

Now i believe the binary search will get your answer…

However, if you need index of values rather than the actual values, you may go for mapping these values to their original indices…

If you still need help, refer to following code only after giving it an attempt

Hope that helps…

import java.util.*;

class Main{

public static void main(String[] args){

    Scanner in = new Scanner(System.in);

    int N = in.nextInt();

    ArrayList<Long> s = new ArrayList<>();

    long c = in.nextLong();

    s.add(c);

for(int i = 1; i < N; i++){

long x = in.nextLong();

if(x <= c)continue;

s.add(x);

c = x;

}

    int Q = in.nextInt();

    while(Q-->0){

        long M = in.nextLong();

        if(s.get(0) >= M)System.out.println(s.get(0));

        else if(s.get(s.size()-1) < M)System.out.println(-1);

        else System.out.println(search(s, M, 0, s.size()-1));

    }

}

static long search(ArrayList<Long> s, long M, int l, int r){

    int mid = (l+r)/2;

    if(s.get(mid) >= M && (mid == 0 || s.get(mid-1) < M))return s.get(mid);

    else if(s.get(mid) < M)return search(s, M, mid+1, r);

    else return search(s,M, l,mid-1);

}

}

6 Likes

what if the array can’t be sorted. also I can use count sort because numbers can be big < 10^12. Let us suppose the array can’t be sorted as N is 10^7 and O(nlogn) sorting will not work

1 Like

@vivek96 can you explain further?

Are you sure \mathcal{O}(n \log n) will not work?
If you provide the problem source it will be helpful.

thanks a lot

yes i am sure

No problem :slight_smile:

thanks.