算法之折半查找（二分法）

算法背景：

binarySearch折半查找算法，也称作二分法，是一种运用于顺序存储结构中的搜索算法，比如有序数组。

算法思想：

1.首先从有序数组中间值开始搜索，如果该位置的值刚好等于要查找的值，则返回结果，搜索结束

2.当要查找得值大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤1的操作。

时间复杂度：o(n)

非递归算法：

/**
*非递归方法
*参数 arr为int型有序数组{5,9,15,33,50,66,79}
*    key为要查找的值
*返回值 返回值为目标值索引
*/
    public static int testBindarySearch(int[] arr, int key){
        int low =0;                 //数组最小值的索引
        int hight = arr.length-1;    //数组最大值的索引

        while(low<=hight){
            int mid = (int) Math.floor((low+hight)/2);
            if (key==arr[mid]){
                return mid;
            }else if(key>arr[mid]){
                low = mid+1;            //把最小索引变化到中间值+1的位置，即数组的索引范围为(mid+1,hight)
            }else{
                hight=mid-1;             //把最大索引变化到中间值-1的位置，即数组的索引范围为(low,mid+1)
            }
        }

        return -1;    //key值大于hight或小于low时
    }

递归算法：（不推荐使用，因为递归算法是一种直接或者间接地调用自身的算法，虽然代码整洁，但运行效率低，且由于需要为局部量或返回点开辟栈来存储，容易造成栈溢出，报java.lang.StackOverflowError错误）

/**
*递归方法
*参数 arr为int型有序数组{5,9,15,33,50,66,79}
*    key为要查找的值
*返回值 返回值为目标值索引
*/
    public static int testBindarySearch2(int[] arr,int key){
        int low =0;                 //数组最小值的索引
        int high= arr.length-1;    //数组最大值的索引

        if(low>high){return -1;}
        int mid= (int) Math.floor((low+high)/2);
        if(key==arr[mid]){
            return mid;
        }else if(key<arr[mid]){
            high=mid-1;
            return testBindarySearch2(arr,key);
        }else{
            low=mid+1;
            return testBindarySearch2(arr,key);
        }
    }