CSC 2200 Lecture Notes - Lecture 21: Binary Search Algorithm, Linear Search, Search Algorithm

22 views3 pages
Published on 19 Jul 2018
Course
CSC 2200 Lecture 21
Interpolation search
Interpolation search
o Is an improved variant of binary search
o Works on the probing position of the required value
o For this algorithm to work properly, the data collection should be in a sorted form and
equally distributed
o Binary search has a huge advantage of time complexity over linear search
o Linear search has worst-case complexity of O(n) whereas binary search has O(log n)
Positioning in Binary Search
o In binary search, if the desired data is not found then the rest of the list is divided in two
parts, lower and higher
o The search is carried out in either of them
o Even when the data is sorted, binary search does not take advantage to probe the
position of the desired data
Position probing in interpolation search
o Interpolation search finds a particular item by computing the probe position
o Initially, the probe position is the position of the middle most item of the collection
o If a match occurs, then the index of the item is returned
To split the list into two parts, we use the following method
Mid=Lo+((Hi-Lo)/(A[Hi]-A[Lo])))*(X-A[Lo])
A=list
Lo=lowest index of the list
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.