循环有序数组查找

循环有序数组查找

• 题目：循环有序数组就是类似于56781234这样的数组。用logn复杂度查找一个元素，并返回其下标；如果不存在则返回-1.
• 思路：有序数组容易想到二分查找。但是需要加一些细节判断。

1. 第一种情况：mid值落在前半部分有序数组中，那么继续判断要查找的n是否落在start和mid中间有序数组部分：是，那么end=mid-1;否则start=mid+1,向后半部分区域查找
2. 第二种情况：mid值落在后半部分有序数组，通过a[mid]>a[start]可以判断，继续判断n是否落在mid和end之间：是，那么start=mid+1,否则end=mid-1,向前寻找。

• 要注意的是除了要判断a[mid]是否等于n之外，还要判断a[start]和a[end]。

    public static int binarySearch(int a[],int n) {
        if(a==null||a.length==0)
            return -1;
        int start=0,end=a.length-1;
        int mid=(start+end)/2;
        while(start<=end) {
            if(a[start]==n)
                return start;
            if(a[end]==n)
                return end;
            if(a[mid]==n)
                return mid;
            mid=(start+end)/2;
            if(a[start]<a[mid]) {
                if(a[start]<n&&a[mid]>n)
                    end=mid-1;
                else
                    start=mid+1;
            }else {
                if(a[mid]<n&&n<a[end])
                    start=mid+1;
                else
                    end=mid-1;
            }
            
        }
        return -1;
    }