gold-10-3

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

示例2:

输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）

提示:

1. arr 长度范围在[1, 1000000]之间

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int search(int[] arr, int target) {
        return doSearch(arr, 0, arr.length - 1, target);
    }

    private int doSearch(int[] arr, int start, int end, int target) {
        if (start == end) {
            return arr[start] == target ? start : -1;
        }

        if (start + 1 == end) {
            if (arr[start] == target) {
                return start;
            } else if (arr[end] == target) {
                return end;
            } else {
                return -1;
            }
        }

        int mid = start + (end - start) / 2;
        if (arr[start] == arr[mid] && arr[mid] == arr[end]) {
            int left = doSearch(arr, start, mid, target);
            int right = doSearch(arr, mid, end, target);
            if (left != -1) {
                return left;
            } else {
                return right;
            }
        } else if (arr[start] <= arr[mid] && arr[mid] <= arr[end]) {
            if (arr[mid] < target) {
                return doSearch(arr, mid, end, target);
            } else {
                return doSearch(arr, start, mid, target);
            }
        } else if (arr[start] >= arr[mid] && arr[mid] <= arr[end]) {
            if (arr[mid] >= target || arr[end] <= target) {
                return doSearch(arr, start, mid, target);
            } else {
                return doSearch(arr, mid, end, target);
            }
        } else {
            if (arr[end] >= target || arr[mid] < target) {
                return doSearch(arr, mid, end, target);
            } else {
                return doSearch(arr, start, mid, target);
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)