data structures using else if (arr[mid]>numend mid- else beg mid+ if (beg end &found = printf("\ % does not exist in the array"num)return int smallest(int arr[]int kint nint pos ksmall=arr[ ]ifor( = + ; < ; ++if(arr[ ]smallsmall arr[ ]pos ireturn posvoid selection_sort(int arr[],int nint kpostempfor( = ; < ; ++pos smallest(arrkn)temp arr[ ]arr[karr[pos]arr[postemp interpolation search interpolation searchalso known as extrapolation searchis searching technique that finds specified value in sorted array the interpolation_search (alower_boundupper_boundvalconcept of interpolation search is similar to how we search for names in step [initializeset low lower_boundtelephone book or for keys by which high upper_boundpos - book' entries are ordered for examplestep repeat steps to while low <high when looking for name "bharatin step set mid low (high lowx telephone directorywe know that it will ((val [low]( [higha[low])be near the extreme leftso applying step if val [midpos mid binary search technique by dividing the print pos list in two halves each time is not good go to step idea we must start scanning the extreme else if val [midleft in the first pass itself set high mid in each step of interpolation searchelse the remaining search space for the set low mid value to be found is calculated the [end of if[end of loopcalculation is done based on the values step if pos - at the bounds of the search space and the print "value is not present in the arrayvalue to be searched the value found at [end of ifthis estimated position is then compared step exit with the value being searched for if the two values are equalthen the search is figure algorithm for interpolation search complete