Polynomial Search
Hi!
Recently I am trying to write programs to search numbers in a list.
I could design a Linear Search. It worked Correct.
I could design a Binary Search. It worked Correct.
But I have no idea how to write Polynomial Search. I searched on Google and I couldn't find any algorithm and I asked our teacher and he said "It's soon for you kid!!!!!!!"
May someone please tell me how can I write a Polynomial Search Program?
I mean an algorithm or flowchart or a hint or ...!
Thanks!
Recently I am trying to write programs to search numbers in a list.
I could design a Linear Search. It worked Correct.
I could design a Binary Search. It worked Correct.
But I have no idea how to write Polynomial Search. I searched on Google and I couldn't find any algorithm and I asked our teacher and he said "It's soon for you kid!!!!!!!"
May someone please tell me how can I write a Polynomial Search Program?
I mean an algorithm or flowchart or a hint or ...!
Thanks!
What exactly do you think "polynomial search" means? Because what it usually means is to search for polynomials.
No!
I mean maybe!
But Our teacher said it is the fastest search for ordered numbers.
Something faster than Binary search and it is almost smart!
Consider a book!
It is 600 pages and you are looking for page 410.
In binary search you get the average of 1 and 600, it is 300, (less than 410), again you get the average of 300 & 600, it is 450 (more than 410) again you get the average of 450 & 300 & ...
BUT in Polynomial search you know 410 is a little after than half of the book, and you accidentally bring the page 400, then 10 pages later is where you are looking for!
This is the exact example our teacher told us!
(Sorry if my English is terrible)
I mean maybe!
But Our teacher said it is the fastest search for ordered numbers.
Something faster than Binary search and it is almost smart!
Consider a book!
It is 600 pages and you are looking for page 410.
In binary search you get the average of 1 and 600, it is 300, (less than 410), again you get the average of 300 & 600, it is 450 (more than 410) again you get the average of 450 & 300 & ...
BUT in Polynomial search you know 410 is a little after than half of the book, and you accidentally bring the page 400, then 10 pages later is where you are looking for!
This is the exact example our teacher told us!
(Sorry if my English is terrible)
Interpolation search, then:
http://en.wikipedia.org/wiki/Interpolation_search
The "faster than binary search" bit is debatable. For sequences of random numbers, yes, on average it's faster. But there are non-random sequences where it performs much worse than binary search.
http://en.wikipedia.org/wiki/Interpolation_search
The "faster than binary search" bit is debatable. For sequences of random numbers, yes, on average it's faster. But there are non-random sequences where it performs much worse than binary search.
Topic archived. No new replies allowed.