Datastructure related. Find all arrays elements greater than or equal to given input

Question

I have a long sequence of order amounts, 1000, 3000, 50000, 1000000, etc.

I want to find out all orders whose amount is more than 100000.

Simplest solution can be iterate through full list and compare and put matched on into another list which will give you all whose amount > 100000.

Do we have any other data structure or algorithm approach which can solve this faster?

The sequence of input elements in unordered.

Answer 1

The approach that comes to mind could be to keep an ordered list of the orders and perform a binary search for the limit amount. All orders before that point in the ordered list will be less than the limit amount.

// Generate a random array of numbers
Random r = new Random();
Integer[] numbers = new Integer[r.nextInt(100) + 20];
for (int i = 0; i < numbers.length; i++) {
    numbers[i] = r.nextInt(50000) + 100;
}
// Order the array and print it
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));
// Find the index of the amount limit (10000 in this case)
int index = Arrays.binarySearch(numbers, 10000);
// Print the slice of array that is lower than the limit amount
System.out.println(Arrays.toString(Arrays.copyOfRange(numbers, 0, Math.abs(index) + 1)));

Answer 2

There are a lot of data structures which can give you a better search time like Tree, HashSet ...etc.

But if you always want get the orders amounting more than 100k, then you can very easily have 2 lists (one for orders < 100k and the other for > 100k). But this is very specific to a case where search amount is constant always and not a general solution.

Answer 3

It depends on how many times you're going to go over the order sequence, and whether it gets modified a lot.

If you're only going to do this once, simple go over the entire sequence and count. It'll be faster than building any other data structure, as you'll have to go over all the orders anyway.

Also, traversing a list of one million items is going to be pretty fast even if you do it repeatedly. Are you sure you have a performance problem here?