[JAVA]斐波那契搜尋(Fibonacci search)

2022-06-12 置頂文章

143
0
algorithm

  // 進行FibonacciSearch前提，先準備好有序陣列
  // 透過斐波那契數列取得變動的中間索引
  // f[k]會配合待排序陣列之長度

import java.util.Arrays;

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

  /**
   * 在陣列中找到目標值即回傳索引
   * 找不到即回傳-1
   * 取得動態中間索引公式：middle = low + f[k-1] - 1
   * @param array
   * @param value
   * @return
   */
  public static int doFibonacciSearch(int[] array, int value) {
    // 初始化參與取得中間索引的參數
    int middle = 0;
    int low = 0;
    int k = 0;
    int high = array.length-1;

    int[] f = getFibonacciArr(20);
    // 當array.length小於f[k]，代表對應的斐波那契數列之索引已經找到
    while(array.length > f[k]) {
      k++;
    }
    // 取得斐波那契數列之索引會比待排序陣列長度還大，因此陣列需以tempArr擴容
    // 待排序陣列array複製一份到tempArr，剩下的位置會放0
    int[] tempArr = Arrays.copyOf(array, f[k]);
    // 把tempArr放0的那些位置，改放待排序陣列的最大值
    for (int i = high+1; i < tempArr.length; i++) {
      tempArr[i] = tempArr[high];
    }

    // 使用迴圈將查找目標值value
    while(low <= high) { // 繼續查找
      if (k == 0) {
        // 代表待排序陣列長度為1
        middle = low;
      } else {
        // 以公式重新設定middle
        middle = low + f[k-1] - 1;
      }

      if (value < tempArr[middle]) { // 向左查找
        // 重新設定high
        high = middle - 1;
        k--;
      } else if (value > tempArr[middle]) { // 向右查找
        // 重新設定low
        low = middle + 1;
        k -= 2;
      } else { // 找到目標索引值
        if (middle <= high) {
          return middle;
        } else {
          return  high;
        }
      }
    }
    return -1;
  }

  /**
   * 取得斐波那契數列
   * @param maxSize
   * @return
   */
  public static int[] getFibonacciArr(int maxSize) {
    int[] f = new int[maxSize];
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i < maxSize; i++) {
      f[i] = f[i-1] + f[i-2];
    }
    return  f;
  }

}

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

回首頁