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

22 views3 pages
Published on 19 Jul 2018
School
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.