Question

can any one tell me a real examples or applications of linear search and interpolation search. thank you.

Answer 1

Interpolation search

The Basic Idea nterpolation search models how humans search a dictionary better than a binary search, because if a human were to search for "Yellow', they would immediately flip towards the end of the dictionary to find that word, as opposed to flipping to the middle. This is the fundamental idea of how interpolation search works. Suppose for simplicity that we have a sorted array of 1000 integers coming from a uniform distribution of integers in the range 0, 10000), and we wanted to find the number 2015. Based on this information, you'd expect to find 2015 around index 201 or 202 because 2015-1000

Pseudocode: 1 interpolation_search(A[0.n-1], x): 4 if x <1o: return -1 if x >= hi : while i mid 12 13 14 15 16 17 18 19 lo = mid elif x < mid: hi-mid else: return k

Application As I said already this algorithm is extremely interesting and very appropriate in many use cases. Here's an example where interpolation search can be used. Let's say there's an array with user data, sorted by their year of birth. We know in advance that all users are born in the 80's. In this case sequential or even binary search can be slower than interpolation search Slist - array( 0 => array('year' s) 1980, 'name' => ' John Smith', 'username ' => 'John'), 1 ->array ('year' 1980, ..) 10394- array ('year 1981, 'name'Tomas M.', ...), 48489array('year' 1985' name 'James Bond', 2808008-array('year1990 "name' 'W.A. Mozart', ...) Now if we search for somebody born in 1981 a good approach is to use interpolation search.

Linear search:-

Linear Search A linear search is the most basic of search algorithm you can have. A linear search sequentially moves through your collection (or data structure) looking for a matching value Implementation function findIndex (values, target) for(var i i values.length ; ++İ){ return ih 0; < if (values[i] target) return -1; findIndex([7, 3, 6, 1, 0], 6)

In The Real World Despite its less than stellar performance, linear searching is extremely common. Many of the built-in methods that you are familiar with, like ruby's find_index , or much of jQuery, rely on linear searches. When you are dealing with a relatively small set of data, it's often good enough (and for really small unordered data is can even be faster than alternatives) Beyond this though, the general concept of sequential/linear access is something that is often overlooked. The more abstract libraries get, the more risk you run of unknowingly doing something linearly. .NET's LINQ is a great example Most of LINQ works against IEnumerable which only exposes a forward moving enumerator. So what do you think happens when you call the Count) method? Thankfully, LINQ is smart and, if possible, it'll rely on a fast count Or Length property However, if the actual implementation doesn't have those, it'll loop through the enumerator. That doesn't make LINQ's Any, or Ruby's include? "evil". It's just good to know what these high level methods might be doing (and often, what they are doing, is a linear search)
Thank you.