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

22 views3 pages

Published on 19 Jul 2018

School

Department

Course

Professor

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