Una búsqueda lineal tiene una complejidad de tiempo O(n). Si se sabe que la lista está ordenada, y suponiendo que admita un acceso aleatorio O(1) (por ejemplo, se implementa como una matriz en la memoria continua), podría usar la búsqueda binaria con una complejidad de tiempo de O(log(n)) .

Si la lista está ordenada, entonces podría usar la búsqueda binaria. En el peor de los casos O(log n) y en el mejor de los casos O(1).

Ejemplo de implementación iterativa:

 public int binSearch(int[] sortedArr, int k, int l, int h) { int i = Integer.MAX_VALUE; while (l <= h) { int mid = (l + h) / 2; if (sortedArr[mid] < k) { low = mid + 1; } else if (sortedArr[mid] > k) { high = mid - 1; } else if (sortedArr[mid] == k) { i = mid; break; } } return i; }

Si tiene una distribución uniforme de números aleatorios, puede hacer todo lo posible y utilizar la búsqueda por interpolación

Código de wikipedia

 /* T must implement the operators -, !=, ==, >=, <= and < such that >=, <=, !=, == and < define a total order on T and such that (tm - tl) * k / (th - tl) is an int between 0 and k (inclusive) for any tl, tm, th in T with tl <= tm <= th, tl != th. arr must be sorted according to this ordering. \returns An index i such that arr[i] == key or -1 if there is no i that satisfies this. */ template <typename T> int interpolation_search(T arr[], int size, T key) { int low = 0; int high = size - 1; int mid; while ((arr[high] != arr[low]) && (key >= arr[low]) && (key <= arr[high])) { mid = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low])); if (arr[mid] < key) low = mid + 1; else if (key < arr[mid]) high = mid - 1; else return mid; } if (key == arr[low]) return low ; else return -1; }