Какую структуру данных построишь для поиска целочисленного значения в массиве без сортировки

Для поиска в неотсортированном массиве оптимальна линейная структура данных (обычный массив или ArrayList), так как другие структуры не дадут преимущества. Поиск будет выполняться за O(n) в худшем случае.

Пример:

int[] arr = {5, 2, 9, 1, 7};
int target = 9;

boolean found = false;
for (int num : arr) {
    if (num == target) {
        found = true;
        break;
    }
}
System.out.println("Found: " + found);

Если поиск нужно выполнять часто, лучше предварительно отсортировать массив (O(n log n)) и использовать бинарный поиск (O(log n)), либо использовать HashSet для O(1) поиска, но это требует дополнительной памяти.