[JAVA]插值搜尋(Interpolation search)

2022-06-07 置頂文章

  // 進行InterpolationSeach前提，先準備好有序陣列
  // 優勢：適合用於陣列值為較連續的、值的差距不大、資料量大
  // 唯有取得中間值公式與二分搜尋不同，剩餘作法一致

// 插值搜尋
public class InterpolationSearch {

  public static void main(String[] args) {
    int[] array = {1,4,23,23,23,56,356,754,975};
    int index = doInterpolationSearching(array, 0, array.length-1, 975);
    System.out.println("index = " + index);
  }

  /**
   * 在陣列中找到目標值即回傳索引
   * 找不到即回傳-1
   * @param array
   * @param left
   * @param right
   * @param value
   * @return
   */
  public static int doInterpolationSearching(int[] array, int left, int right, int value) {
    System.out.println("call function now~");
    // 由於目標值(value)有參與中間值索引(middle)計算，怕索引越界，所以必須防呆
    if (left > right || value < array[0] || value > array[array.length-1]) {
      return -1;
    }
    // 中間索引
    int middle = left + (right - left) * (value - array[left]) / (array[right] - array[left]);
    int middleVal = array[middle];
    if (value < middleVal) { // 向左遞歸
      return doInterpolationSearching(array, left, middle-1, value);
    } else if (value > middleVal) { // 向右遞歸
      return doInterpolationSearching(array, middle+1, right, value);
    } else {
      return middle;
    }
  }

}

如有敘述錯誤，還請不吝嗇留言指教，thanks!

回首頁