二分查找：在旋转有序的数组中查找元素

旋转有序的数组

二分查找：在旋转有序的数组中查找元素
1,3,5,7,9,11,13,15,17,19 ==》11,13,15,17,19,1,3,5,7,9
会在某个节点旋转成这个样子，你可以理解为截断，然后拼接

代码

public class Test3 {
    /**
     * 在旋转有序的数组中查找元素
     * 1,3,5,7,9,11,13,15,17,19 ==》11,13,15,17,19,1,3,5,7,9
     * 会在某个节点旋转成这个样子，你可以理解为截断，然后拼接
     *
     * @param num
     * @param target
     * @return
     */
    public static int getIndex(int[] num, int target) {
        if (null == num || num.length == 0) {
            return -1;
        }
        int start = 0;//用于二分查找的数组开始节点，随着循环每次范围变小
        int end = num.length - 1;//用于二分查找的数组结束节点，随着循环每次范围变小
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (num[mid] == target) {
                return mid;
            }
            if (num[mid] > num[start]) {//mid在第一个有序数组里
                if (target <= num[mid] && target >= num[start]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {//mid在第二个有序数组里
                if (target >= num[mid] && target <= num[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (num[start] == target) {
            return start;
        }
        if (num[end] == target) {
            return end;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] num = {11,13,15,17,19,1,3,5,7,9};
        System.out.println(getIndex(num, 3));
    }
}

图解