CODEWITHSUNDEEP
algorithmsortingdata-structures
Peter Mel
Peter Mel

Reputation: 367

Search in ordered list

Assume we have a list 0, 10, 30, 45, 60, 70 sorted in ascending order. Given a number X how to find the number in the list immediately below it?

I am looking for the most efficient (faster) algorithm to do this, without of course having to iterate through the whole list.

Ex: [0, 10, 30, 45, 60, 70]

Given the number 34, I want to return 30.
Given the number 30, I want to return 30.
Given the number 29, I want to return 10.

And so forth.

Upvotes: 1

Views: 10678

Answers (3)

amit
amit

Reputation: 178411

  • If your list is indeed that small, most efficient way would be to create an array of size 71, initialize it once with arr[i] = answer, and in constant query time - just get the answer. The idea is since your possible set of queries is so limited, there is no reason not to pre-calculate it and get the result from the pre-calculated data.

  • If you cannot pre-process, and the array is that small - linear scan will be most efficient for such a small array, the overhead of using complex algorithm does not worth it for such small arrays. Any overhead for more complex algorithms (like binary search) that add a lot of instructions per iteration, is nullified for small arrays. Note that log_2(6) < 3, and this is also the expected time (assuming uniform distribution) to get the result in a linear search, but linear search is so much simpler, each iteration is much faster than in binary search.

Pseudo code:

prev = -infinity
for (x in arr):
   if x>arr: 
       return prev
   prev = x
  • If the array is getting larger, use binary search. This algorithm is designed to find a value (or the first value closest to it) in a sorted array, and runs in O(logn) time, needing to traverse significantly fewer elements than the entire list.
    It will achieve much better results (in terms of time performance) compared to the naive linear scan, assuming uniform distribution of queries.

Upvotes: 7

Gentian Kasa
Gentian Kasa

Reputation: 776

Implement the Binary Search Algorithm where, in case the element is not found, you return the element in the last visited position (if it's smaller than or equal to the given number) or the element in the last visited position - 1 (in case the element in the last visited position is greater than the given number).

Upvotes: 0

Michael Baarz
Michael Baarz

Reputation: 422

Is the list always sorted? Fast to get written or fast in execution time?

Look at this: http://epaperpress.com/sortsearch/download/sortsearch.pdf

Upvotes: 1

Related Questions