一、二分查找

package example.test.find;

import java.util.Arrays;

/**
 * @author Tao
 * @Date 2020/10/20
 * @Time 11:15
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {9, 1, 5, 2, 8, 0, 4, 6};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int target = 2;
        System.out.println(search(arr, 0, arr.length - 1, target));
    }

    private static int search(int[] arr, int left, int right, int target) {
        //使用二分查找的前提是，数组是有序的

        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
//        插值查找算法，自适应mid，在分布较为均匀的有序表中查找效率更高
//        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        if (arr[mid] < target) {
            return search(arr, mid + 1, right, target);
        } else if (arr[mid] > target) {
            return search(arr, left, mid - 1, target);
        } else {
            return mid;
        }
    }
}

二、黄金分割

package example.test.find;

import java.util.Arrays;

/**
 * @author Tao
 * @Date 2020/10/20
 * @Time 11:54
 */
public class FibonacciSearch {
    public static void main(String[] args) {

        int[] arr = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};

        int target = 39;
        int position = search(arr, target);
        System.out.println("值" + target + "的元素位置为：" + position);
    }


    private static int search(int[] arr, int target) {
        //斐波那契查找 ，也成黄金分割法。
        //黄金分割点是指把一条线分割为两部分， 其中一部分与全长之比等于另一部分与这部分之比。
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;

        // 斐波那契分割数值下标
        int k = 0;

        // 获取斐波那契数列
        int[] f = getFibonacci();

        // 获取斐波那契分割数值下标，等于或大于数组长度
        while (high > f[k]) {
            k++;
        }

        // 创建临时数组，扩充原数组并将扩充部分值设为最大值
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = high; i < f[k]; i++) {
            temp[i] = arr[high];
        }

        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (target < temp[mid]) {
                high = mid - 1;
                //往左边，f(k)=f(k-1)+f(k-2)
                k--;
            } else if (target > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }

        }


        return -1;
    }


    private static int[] getFibonacci() {
        int[] f = new int[20];
        int i = 0;
        f[0] = 1;
        f[1] = 1;
        for (i = 2; i < 20; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }


}

Q.E.D.