Interpolation Search algorithm (Interpolation Search)

What is Interpolation Search algorithm (Interpolation Search)?

Interpolation Search (Interpolation Search) is an improved variant of Binary Search (Binary Search). In order for this search algorithm to work correctly, the data set must be sorted.

Binary Search has a great advantage of time complexity when compared to Linear Search. Linear Search has the worst case complexity of Ο (n) while Binary Search is Ο (log n).

There are a number of situations where the location of the data you want to find may already be known. For example, in the case of a phone book, if we want to find Huong's phone number, for example. In this case, Linear Search and Binary Search may be slow when performing a search, when we can directly jump to the memory space whose name begins with H stored.

Locate in Binary Search

In Binary Search, if the data to be searched is not found, the rest of the list is divided into two parts: the left part (containing the smaller value) and the right part (containing the larger value). The search process is then performed on one of these two sections.

Interpolation Search algorithm (Interpolation Search) Picture 1

Search for location in Interpolation Search (Interpolation Search)

Search interpolation searching for a specific element by calculating the probe position (Probe Position). Initially, the detector position is the position of the element in the middle of the data set.

Interpolation Search algorithm (Interpolation Search) Picture 2

If a connection is found, the index of the element 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]) Trong đó: A = danh sách Lo = chỉ mục thấp nhất của danh sách Hi = chỉ mục cao nhất của danh sách A[n] = giá trị được lưu giữ tại chỉ mục n trong danh sách

If the element to be found has a value greater than the middle element, the element to be found will be in the sub-array to the right of the middle element and we will continue to calculate the detector position; otherwise, the element to be found will be in the sub-array to the left of the middle element. This process proceeds on sub-arrays until the size of the sub-array decreases to 0.

The Interpolation Search runtime complexity is Ο (log (log n)) , while Binary Search is Ο (log n) .

Interpolation Search algorithm

Because this is an improvement of the Binary Search algorithm, we will only mention the steps to find the index of the value to be searched using the detector position.

 Bước 1  : Bắt đầu tìm kiếm dữ liệu từ phần giữa của danh sách Bước 2  : Nếu đây là một so khớp (một kết nối), thì trả về chỉ mục của phần tử, và thoát. Bước 3  : Nếu không phải là một so khớp, thì là vị trí dò. Bước 4  : Chia danh sách bởi sử dụng phép tính tìm vị trí dò và tìm vị trí giữa mới. Bước 5  : Nếu dữ liệu cần tìm lớn hơn giá trị tại vị trí giữa, thì tìm kiếm trong mảng con bên phải. Bước 6  : Nếu dữ liệu cần tìm nhỏ hơn giá trị tại vị trí giữa, thì tìm kiếm trong mảng con bên trái Bước 7  : Lặp lại cho tới khi tìm thấy so khớp

Sample code for Interpolation Search algorithm

 A → M ả ng N → K í ch c ỡ c ủ a A X → Gi á tr ị c ầ n t ì m h à m t ì m ki ế m n ộ i suy Interpolation_Search () G á n Lo → 0 G á n Mid → - 1 G á n Hi → N - 1 While X kh ô ng so kh ớ p if Lo b ằ ng Hi OR A [ Lo ] b ằ ng A [ Hi ] EXIT : Th ấ t b ạ i , kh ô ng t ì m th ấ y X k ế t th ú c if G á n Mid = Lo + (( Hi - Lo ) / ( A [ Hi ] - A [ Lo ])) * ( X - A [ Lo ]) if A [ Mid ] = X EXIT : Th à nh c ô ng , t ì m th ấ y t ạ i Mid else if A [ Mid ] < X Thi ế t l ậ p Lo th à nh Mid + 1 else if A [ Mid ] > X Thi ế t l ậ p Hi th à nh Mid - 1 k ế t th ú c if k ế t th ú c if K ế t th ú c While K ế t th ú c h à m 

According to Tutorialspoint

Previous article: Binary Search algorithm (Binary Search)

Next lesson: Hash Table data structure