Searching a number in an array in least time

Question

The elements of the array are arranged in non-decreasing order. I need to search the array for a given element in the least possible time.

Answer 1

Use binary search to find it.

Answer 2

Since the array is sorted you can make use of Binary Search.

A linear search will take O(n) time because it does not make use of the sorted property. But a binary search will take O(log n) time.

Answer 3

If all you know is that the array is sorted in non-decreasing order, you can't do better than binary search with its guaranteed O(log N) performance (as pointed out by other posters).

If you can assume a reasonably uniform distribution of numbers in the array, then interpolation search can give O(log log N) performance in the average case, which is better than binary search. (However, in the worst case - an array with exponential growth - it's O(N)).

Answer 4

Well, if you need better than Binary, you -could- use heuristics like Newton Search, which is a derivative of binary search, with moving split border - every time the value is greater, increase the step, if it's smaller, decrease it.

split = 0.5;
while(1)
{
    point = lower+split*(upper-lower);
    if(x>a[point])
    {
        lower = point;
        split*= 1.2
    }
    else if(x<a[point])

    {
        upper=point;
        split /=1.2
    } else break;
}

This supposedly yields better results with sets that have polynomial layouts and unbound sets. It gives worse results with random or linear layouts. This can also crash with split growing above 1 without proper safeguards.