CODEWITHSUNDEEP
c
Mohammad Nadeem
Mohammad Nadeem

Reputation: 9392

Searching a number in an array in least time

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.

Upvotes: 3

Views: 204

Answers (4)

Simon Nickerson
Simon Nickerson

Reputation: 43159

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)).

Upvotes: 0

SF.
SF.

Reputation: 14039

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.

Upvotes: 0

codaddict
codaddict

Reputation: 454960

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.

Upvotes: 2

nos
nos

Reputation: 229058

Use binary search to find it.

Upvotes: 2

Related Questions