Блог

Меня смущает вычисление интерполяционного поиска, программа предоставляет разные результаты шага по сравнению с ручными вычислениями.

Входные данные: {3, 5, 10, 14, 21}

И я хочу найти число 14. Если вычислить вручную, то для поиска 14 потребуется всего 2 шага.

Я пробую это в своей программе интерполяционного поиска

 System.out.println("post low higth "   post   " "   low   " "   hight);  

И он показывает 3 шага, чтобы найти ключ, который я ищу, как показано на следующем рисунке.

Но когда я это сделаю

 System.out.println("mid row col dataMid: "   mid   " "   left   " "   right);  

в двоичном поиске ручные вычисления и циклы в программе одинаковы, они состоят всего из 2 шагов, как показано на следующем рисунке.

Кто — нибудь может объяснить мне, почему это происходит?

Это мой код интерполяционного поиска

 public static void interpolationSearch(int[] arr, int key){  int low,hight,post;  low = 0;  hight = arr.length-1;   while (lowlt;=hight){  post = low ((key-arr[low])/(arr[hight]-arr[low]))*(hight-low);   System.out.println("post low higth "   post   " "   low   " "   hight);  if (key == arr[post]){  System.out.println("Data found");  System.out.println("data ada di indeks ke-: " post);  return ;  }  else if (arr[post]gt;key){  hight = post-1;  }else {  low = post 1;  }  } }  

И это мой двоичный поисковый код

 public static void binarySearch(int arr[], int key) {  int left = 0;  int right = arr.length - 1;   while(left lt;= right) {  int mid = left   (right - left) / 2;   System.out.println("mid left hight: "   mid   " "   left   " "   right);  //divide and conquer  if(key == arr[mid]) {  System.out.println("Data ditemukan!");  return;  } else if(key gt; arr[mid]) {  left = mid   1;  } else {  right = mid - 1;  }  }  System.out.println("Data tidak ditemukan!"); }