搜索旋转数组。给定一个排序后的数组，包含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 （没有找到）
提示:
arr 长度范围在[1, 1000000]之间
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-rotate-array-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
先用二分法找出起始位置，之后用二分法找到第一个值。
private int findMin(int[] nums) { int st = 0; int end = nums.length - 1; while (st < end) { int last = nums[end]; int m = st + ((end - st) >>> 1); if (nums[m] > last) { st = m + 1; } else if (nums[m] < last) { end = m; } else { for (int i = st; i <= end; i++) { if (i != 0 && nums[i - 1] > nums[i]) { return i; } } return st; } } return st; } public int search(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } if (nums[0] == target) { return 0; } int index = findMin(nums); System.out.println(index); int length = nums.length; int st = 0; int end = length - 1; while (st < end) { int m = st + ((end - st) >> 1); int v = m + index; int m1 = v >= length ? v - length : v; if (nums[m1] < target) { st = m + 1; } else { end = m; } } st = st + index >= length ? st + index - length : st + index; if (nums[st] == target) { return st; } return -1; }
原文：https://www.cnblogs.com/wangzaiguli/p/14750488.html