循环数组的二分查找--Java实现

/**
 * 循环数组的二分查找
 * @author Jacky
*测试用数组
 *[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8]
*数组对应下标，方便查看
 *[0,  1,  2,  3, 4,  5,  6,  7,   8,  9, 10, 11,12,13,14,15,16,17,18,19]
 */
public class BSearch2 {
    public static int BSearch(int[] arr,int left,int right,int value) {
        while(left<=right) {
            int mid = left+((right-left)>>1);//防止溢出的取中方法
            if(value<arr[mid]) {
                int lMid = (left+mid)/2;//取左区间的中间值，仅用于判断是否单调增长
                if(arr[0]<=arr[lMid]&&arr[lMid]<=arr[mid]) {//如果此时左区间是单调增长
                    //判断value是否在左边区间，通过与区间另一端的值比较
                    //如果在左边区间
                    if(value>=arr[left]) {
                        //则在左区间做二分查找
                        int result = BSearch(arr,left,mid-1,value);
                        if(result!=-1) return result;//需要对返回值进行判断，否则递归没有出口
                    }else {//如果在右边区间，则要在右区间做二分查找
                        int result = BSearch(arr,mid+1,right,value);
                        if(result!=-1) return result;
                    }
                }else {
                    //在左区间做二分查找
                    int result = BSearch(arr,left,mid-1,value);
                    if(result!=-1) return result;
                }
            }else if(value>arr[mid]) {//同理
                int rMid = (right+mid)/2;
                if(arr[mid]<=arr[rMid]&&arr[rMid]<=arr[right]) {//单调区间
                    if(value<=arr[right]) {//在
                        int result = BSearch(arr,mid+1,right,value);
                        if(result!=-1) return result;
                    }else {//不在
                        int result = BSearch(arr,left,mid-1,value);
                        if(result!=-1) return result;
                    }
                }else {//非单调区间，一定在
                    int result = BSearch(arr,mid+1,right,value);
                    if(result!=-1) return result;
                }
            }else {
                return mid;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int arr[] = {9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8};
        int i = BSearch(arr,0,arr.length-1,8);
        System.out.println(i);
    }
    
}

与普通二分查找的不同：

1. 以上的查找对象为循环数组，而普通二分查找的对象为有序的普通数组；
2. 正因为是循环数组，取中进行判断之后，目标值不一定在普通二分查找所设想的区间，需要进行判断，具体判断如下：

如何判断一段数组是单调递增呢？在该段数组的头、中间、尾三个位置p,m,q取三个值a[p], a[m], a[q]，如果是单调递增则一定满足 a[p] >= a[m] >= a[q]，否则则非单调递增。

判断目标元素下一步所在区间，有几种情况：
当 x > a[m] 时，
右半边是单调递增区间，并且x在此区间内，下一步则可在此右半边区间内查找
右半边是单调递增区间，并且x不在此区间内，下一步在左半边查找
右半边是非单调递增区间，则x必然在此区间内，下一步在右半边查找
当 x < a[m] 时， 同理类似
左半边是单调递增区间，并且x在此区间内，下一步则可在此左半边区间内查找
左半边是单调递增区间，并且x不在此区间内，下一步在右半边查找
左半边是非单调递增区间，则x必然在此区间内，下一步在左半边查找

判断是否在单调递增部分，只需与区间的另外一头的元素比较一下大小即可知道

参考文章：循环有序数组的二分查找