有序数组查找算法：二分法和插值法

/**
 * 有序数组的值查找
 */
public class Search {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,9,10};
        //int i = binarySearch3(arr,  3);
        int i = binarySearch(arr, 91);
        System.out.println(i);
    }

    /**
     * 非递归实现二分查找
     * @param arr
     * @param searchVal
     * @return
     */
    static  int binarySearch(int[] arr,int searchVal){
        //初始化左指针
        int left=0;
        //初始化右指针
        int right=arr.length-1;

        //当右指针小于左指针时，说明没有找到，退出循环
        while(right>=left){
            int middle=(left+right)/2;
            int midVal=arr[middle];
            if(midVal>searchVal){
                right=middle-1;
            }else if(midVal<searchVal){
                left=middle+1;
            }else{
                return middle;
            }
        }
        return -1;
    }

    /**
     * 递归方式进行二分查找
     * @param arr 查找的数组
     * @param left 左指针
     * @param right 右指针
     * @param searchVal 需要查找的值
     * @return 如果查找到了返回该值在数组中的下标。否则返回-1
     */
    static int  binarySearch2(int[] arr,int left,int right, int searchVal ){
        if(left>right){
            return -1;
        }
        int middle=(left + right)/2;
        int midVal=arr[middle];
        if(midVal>searchVal){
            return binarySearch2(arr,left,middle-1,searchVal);
        }else if(midVal<searchVal){
            return  binarySearch2(arr,middle+1,right,searchVal);
        }else{
            return  middle;
        }
    }

    /**
     * 使用栈实现二分搜索
     * 所有的递归都可以用栈来实现。
     * @param arr
     * @param searchVal
     * @return
     */
    static  int binarySearchByStack(int[] arr,int searchVal){
        //初始化左指针
        int left=0;
        //初始化右指针
        int right=arr.length-1;

        Stack<Integer> stack = new Stack<>();
        stack.push(left);
        stack.push(right);

        while(true){
            int curRight= stack.pop();
            int curLeft= stack.pop();

            if(curLeft>curRight){
                return -1;
            }

            int middle=(curLeft+curRight)/2;
            int midVal=arr[middle];
            if(midVal>searchVal){
               // right=middle-1;
                stack.push(curLeft);
                stack.push(middle-1);

            }else if(midVal<searchVal){
               // left=middle+1;
                stack.push(middle+1);
                stack.push(curRight);
            }else{
                return middle;
            }

        }
    }

    /**
     * 插值查找，和二分法类似，但寻找中间值的方式变了。
     * @param arr 查找的数组
     * @param left 左指针
     * @param right 右指针
     * @param searchVal 需要查找的值
     * @return 如果查找到了返回该值在数组中的下标。否则返回-1
     */
    static int insertSearch(int[] arr,int left,int right, int searchVal){
        if(left>right || arr[left]>searchVal || arr[right]<searchVal){
            return -1;
        }
        //和二分法的区别
        int middle = left + (right - left) * (searchVal - arr[left]) / (arr[right] - arr[left]);
        int midVal=arr[middle];
        if(midVal>searchVal){
            return binarySearch2(arr,left,middle-1,searchVal);
        }else if(midVal<searchVal){
            return  binarySearch2(arr,middle+1,right,searchVal);
        }else{
            return  middle;
        }
    }
}