二分查找和插值查找

二分查找

package search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 1000, 1000, 1234};
        System.out.println(binarySearch2(arr, 0, arr.length - 1, 1000));
    }

//查到符合要求的就返回对应的下标
    private static int binarySearch(int[] arr, int left, int right, int target) {
        int mid = (left + right) / 2;
        if (left > right) {
            return -1;
        }
        if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, right, target);
        } else if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else {
            return mid;
        }
    }

//匹配所有符合要求的下标，存放到list集合里面
    private static List binarySearch2(int[] arr, int left, int right, int target) {
        int mid = (left + right) / 2;
        if (left > right) {
            return new ArrayList<>();
        }
        int midVal = arr[mid];
        if (midVal < target) {
            return binarySearch2(arr, mid + 1, right, target);
        } else if (midVal > target) {
            return binarySearch2(arr, left, mid - 1, target);
        } else {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != target) {
                    break;
                }
                arrayList.add(temp);
                temp -= 1; //temp左移
            }
            arrayList.add(mid);
            //右移
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != target) {
                    break;
                }
                arrayList.add(temp);
                temp += 1;
            }
            return arrayList;
        }
    }
}

插值查找

package search;

public class insertValueSearchDemo {
    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 1000, 1000, 1234};
        int index = insertValueSearch(arr, 0, arr.length - 1, 1000);
        System.out.println(index);
    }


    /**
     * @param arr    数组
     * @param left   左边索引
     * @param right  右边索引
     * @param target 目标值
     * @return 如果找到，就返回对应的下标，如果没有找到，返回-1
     */
    private static int insertValueSearch(int[] arr, int left, int right, int target) {
        if (left > right || target < arr[0] || target > arr[arr.length - 1]) {
            return -1;
        }
        //求出自适应的mid
        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (target > midVal) {//向右边递归
            return insertValueSearch(arr, mid + 1, right, target);
        } else if (target < midVal) {
            return insertValueSearch(arr, left, mid - 1, target);
        } else {
            return mid;
        }
    }
}