How to search a very large array in C++ for a particular value?

Question

I was asked this question by an interviewer. How can I search a large array (thousands maybe millions of values) for a particular value.

I suggested binary search for cases in which the items are sorted and the array size is smaller. I also suggested 1 iteration for the bubble sort algorithm if you want the largest value in a large array (value is to the rightmost after 1 pass).

But I am unsure what algorithms can extract a value within an inherently random assortment of array indices.

Answer 1

1. Linear search. This will take O(n). It should be good enough if the array size is in the range of thousands and millions.

2. If you do search operations more often. You might want to convert your array into a hashtable. Building the hashtable will take O(n) at first, then every search operation will take O(1). Solution 1 will take O(n) for every search operation you do.

3. If the array is really large you can utilize multiple threads to search the array concurrently. Divide the array into parts and each thread searches its part for the value.