数据查询

/* 二分查找（前提数组是有序数组） */
function binarySearch(arr,target){
    var minIndex = 0;
    var maxIndex = arr.length - 1;
    if(arr.length == 0 || target <arr[0] || target > arr[arr.length -1 ])return false;
    while(minIndex <=maxIndex){
        var mid = Math.floor((maxIndex+minIndex) / 2)
        if(arr[mid] == target){
            return true
        }else if(arr[mid] > target){
            maxIndex = mid - 1
        }else{
            minIndex = mid + 1
        }
    }
    return false
}

/* 插入查找（前提数组不重复并且是有序数组） */
//目标下标 = （目标值 - 最小值） / （最大值-最小值） *（最大下标- 最小下标） + 最小下标
function interpolationSearch(arr,target){
     var minIndex = 0;
    var maxIndex = arr.length - 1;
    if(arr.length == 0 || target <arr[0] || target > arr[arr.length -1 ])return false;
    while(minIndex <=maxIndex){
        var mid = (target - arr[minIndex]) /(arr[maxIndex] - arr[minIndex]) *(maxIndex - minIndex) + minIndex
        if(arr[mid] == target){
            return true
        }else if(arr[mid] > target){
            maxIndex = mid - 1
        }else{
            minIndex = mid + 1
        }
    }
    return false
}