Tìm kiếm nội suy

1int interpolationSearch(int[] arr, int target) {2  int left = 0, right = arr.length - 1;  // Toàn dải tìm kiếm3  while (left <= right && target >= arr[left] && target <= arr[right]) {  // Target trong dải4    int pos = left + (target-arr[left])*(right-left)/(arr[right]-arr[left]);  // Ước lượng vị trí dò5    if (arr[pos] == target) return pos;  // Tìm thấy6    else if (arr[pos] < target) left = pos + 1;  // Tìm phần trên7    else right = pos - 1;  // Tìm phần dưới8  }9  return -1;  // Không có trong mảng10}