Interpolation Search

Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in sorted and equally distributed form.

• C#
• VB.Net
• C
• C++
• PHP

									Public Shared Function Search(list As Integer(), data As Integer) As Integer
	Dim lo As Integer = 0
	Dim mid As Integer = -1
	Dim hi As Integer = list.Length - 1
	Dim index As Integer = -1

	While lo <= hi
		mid = CInt(Math.Truncate(lo + ((CDbl(hi - lo) / (list(hi) - list(lo))) * (data - list(lo)))))

		If list(mid) = data Then
			index = mid
			Exit While
		Else
			If list(mid) < data Then
				lo = mid + 1
			Else
				hi = mid - 1
			End If
		End If
	End While

	Return index
End Function
								

Example

									Dim list As Integer() = {14, 26, 43, 72, 321}
Dim index As Integer = Search(list, 72)
								

Output

									index: 3