A linear search has an O(n) time complexity. If the list is known to be ordered, and assuming it supports an O(1) random access (e.g., it's implemented as an array in continuous memory), you could use binary search with a time complexity of O(log(n)).

If the list is ordered then you could use binary search. Worst-case O(log n) and best case O(1).

Example iterative implementation:

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;
}

If you have an uniform distribution of random numbers you could go all out and use interpolation search

Code from 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;
}