如果列表是有序的，那么可以使用二进制搜索。最坏情况o（logn）和最佳情况o（1）。
迭代实现示例：

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

线性搜索的时间复杂度为o（n）。如果已知列表是有序的，并且假设它支持o（1）随机访问（例如，它实现为连续内存中的数组），则可以使用时间复杂度为o（log（n））的二进制搜索。

如果你有一个均匀分布的随机数，你可以全力以赴，并使用插值搜索
来自维基百科的代码

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