二分查找

二分法查找的原理很简单，先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找。适用于数据量大大场景，但是要求数据有序。

public class BinarySearch {
    
    public static int search(int[] arr,int target) {
        if(arr == null || arr.length <= 0) return 0 ;
        int low = 0;
        int high = arr.length - 1;
        while(low < high) {
            int mid = (low + high) >> 1;
            if(arr[mid] == target) return mid;
            if(target < arr[mid]) {
                high = mid - 1;
            }
            if(target > arr[mid]) {
                low = mid + 1;
            }
        }
        return 0;
    }
}

改进版：插值查找

当我们知道要查找的数据大概在什么位置的时候，就没必要从中间找了。插值查找和普通的二分查找的区别就在于中间值的选择。

    public static int insertSearch(int[] arr, int target) {
        if(arr == null || arr.length <= 0) return 0 ;
        int low = 0;
        int high = arr.length - 1;
        while(low < high) {
            if(low == high) {
                if(arr[low] == target) {
                    return low;
                }
                return -1;
            }
            int mid = low + ((target - arr[low])/(arr[high] - arr[low]))* (high - low);
            if(arr[mid] == target) return mid;
            if(target < arr[mid]) {
                high = mid - 1;
            }
            if(target > arr[mid]) {
                low = mid + 1;
            }
        }
        
        return -1;
    }