Most efficient way to search integer array in Java

Question

I'm looking for the most efficient way to determine whether a specific value exists in a small (16 element) array of integers in Java. The array is unsorted.

Options:

A boring but reliable for loop
Sort the array then Arrays.binarySearch(arr, targetVal)
List.contains method - example Arrays.asList(arr).contains(targetVal)
Something else.

Option 3 must have some overhead in "converting" to a List but I could use a List throughout rather than an array if that would be better overall. I've no feel for how List performs speed wise.

KISS principle -> For only 16 elements a boring loop it's just enough — Ele
– Ele, Commented Jun 21, 2022 at 7:27
Option 1, unless you sort it only once and then you are going to search it many times, in which case option 2. — rghome
– rghome, Commented Jun 21, 2022 at 7:38
Unless you identify the array searching as an important hotspot in your software, it doesn't matter one bit. As soon as you do anything more complex (data access, calculations, etc.), any differences in array searching performance is lost and any time you've spent on this is wasted. — Kayaman
– Kayaman, Commented Jun 21, 2022 at 7:39
@rghome it's important knowledge for the beginners (and bad programmers) who think that micro-optimization matters, parallelization makes things automatically faster, don't understand differences between CPU and IO constrained work and so on. Also, I wasn't asking, I was telling. — Kayaman
– Kayaman, Commented Jun 21, 2022 at 7:52
Normally, audio processing is done on small blocks, rather than once per sample. — Holger
– Holger, Commented Jun 21, 2022 at 15:46

Stanislau Kozel · Accepted Answer · 2022-06-21 07:33:31Z

3

Based on condition that the array is unsorted any search on it will have complexity O(n). You can try use your second assumption. In that case you will have O(n*log(n)) + O(log(n)) But if you have such small array and you want to search only once better to use a simple loop. Because it hard to predict what time will be elapsed for conversion to List or what type of sorting algorithm will you use and etc. Just a loop will be a good choice

FYI: Stream will not be efficient at your case.

answered Jun 21, 2022 at 7:33

Stanislau Kozel

1666 bronze badges

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

1 Comment

Holger Over a year ago

Obviously, O(n*log(n)) + O(log(n)) is not better than O(n), so it’s not really worth a try.

Collectives™ on Stack Overflow

Most efficient way to search integer array in Java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related