在有序的序列中，每次都以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

非递归实现

public static Integer cycleSearch(int arr[], int target) {
        //定义开始位置
        int start = 0;
        //定义结束位置
        int end = arr.length - 1;

        while (start <= end) {
            //计算中位数
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return arr[mid];
            } else if (arr[mid] < target) {
                //如果中位数元素小于目标值，则将起始位置设置为mid++
                start = mid++;
            } else if (arr[mid] > target) {
                //如果中位数元素大于目标值，则将结束位置设置为mid--
                end = mid--;
            }
        }

        return -1;
    }

递归实现

public static Integer recursiveSearch(int start, int end, int[] arr, int target) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) {
            return arr[mid];
        }else if (arr[mid] > target){
            return recursiveSearch(start,mid--,arr,target);
        }else if (arr[mid] < target){
            return recursiveSearch(mid++,end,arr,target);
        }
        return -1;
    }

复杂度

时间复杂度

最坏的情况下两种方式时间复杂度一样：O(log2 N)

空间复杂度

非递归方式：
由于辅助空间是常数级别的所以：
空间复杂度是O(1);

递归方式：
递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：
空间复杂度：O(log2N )

中位数的计算

常用的写法。如果两个数太大，会有溢出的风险

public static int  avg(int x ,int y){
    return (x+y)/2;
}

正确的写法。把求平均数分成了2部分，a&b和a ^ b>>1，a&b相同的部分，a^b的差值，差值右移一位算出平均值，然后相加即可。

public static int avg(int a,int b){
   return ((a&b) + ((a^b) >> 1));
}

在二分查找里，a一定是小于b的，所以可以这样

public static int avg(int a,int b){
    // a <=b
   return  a+(b-a)/2;
}