假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4

示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

//主要是找到单调区间，通过mid与left对应的值大小进行判断，判断单调区间的位置，进行范围的缩小，注意在left，right边界处是有可能相同的。

class Solution { 
    public int search(int[] nums, int target) { 
    if(nums == null || nums.length == 0) return -1; int left = 0, right = nums.length -1; int mid; while(left <= right){ 
   //这里的等号一定要加上，因为不一定存在 mid = left + (right - left)/2; if(nums[mid] == target){ 
    return mid; } //主要判断mid是落在哪个范围上 if(nums[mid] >= nums[left]){ 
   //因为有可能mid = left，当只有一个值的时候，所以要加上等号，捕捉到这个情况，不然将转到else当中，找不到具体的值 //若在一个单调的闭合的范围,因为不知道旋转数组的分界线究竟在哪，所以要依靠两端进行判断 if(target >= nums[left] && target < nums[mid]){ 
   //nums[mid]一定不等于target right = mid -1; }else{ 
    left = mid + 1; } }else{ 
   // if(target > nums[mid] && target <= nums[right]){ 
    left = mid + 1; }else{ 
    right = mid - 1; } } } return -1; } } 

也可以对右边判断，nums[mid] <= nums[right]，只要不能全部通过，一般是在[mid, right]区间，两种结局方案，忘记加等号
2.int mid = left +(right - left + 1) /2对上取整，一般就可以通过了

讯享网class Solution { 
    public static void main(String[] args) { 
    Solution ss = new Solution(); int[] num = { 
   3,1}; System.out.println(ss.search(num, 1)); } public int search(int[] nums, int target) { 
    if(nums == null || nums.length == 0) return -1; int left = 0, right = nums.length -1; int mid; while(left <= right){ 
   //这里的等号一定要加上，因为不一定存在 mid = left + (right - left)/2; if(nums[mid] == target){ 
    return mid; } //主要判断mid是落在哪个范围上 if(nums[mid] <= nums[right]){ 
    //若在一个单调的闭合的范围,因为不知道旋转数组的分界线究竟在哪，所以要依靠两端进行判断 if(target > nums[mid] && target <= nums[right]){ 
    left = mid + 1; }else { 
    right = mid - 1; } }else{ 
   // if(target >= nums[left] && target < nums[mid]){ 
   //nums[mid]一定不等于target right = mid -1; }else{ 
    left = mid + 1; } } } return -1; } } 

L81

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true 示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false 进阶:

这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

讯享网

区别就在于相等的时候需要独立判断，在于元素可能会重复

class Solution { 
    public boolean search(int[] nums, int target) { 
    if(nums == null || nums.length == 0) return false; int left = 0, right = nums.length -1; int mid; while(left <= right){ 
   //这里的等号一定要加上，因为不一定存在 mid = left + (right - left)/2; if(nums[mid] == target){ 
    return true; } //主要判断mid是落在哪个范围上,注意这个时候的范围要更详细些， //因为存在重复元素 if(nums[mid] > nums[left]){ 
   //不再取等号，如1,3,1,1,1寻找3 if(target >= nums[left] && target < nums[mid]){ 
    right = mid -1; }else{ 
    left = mid + 1; } }else if(nums[mid] < nums[left]){ 
   //若在第二个有序范围内,或者写成nums[mid] < nums[right]一样成立能通过哦 if(target > nums[mid] && target <= nums[right]){ 
    left = mid + 1; }else{ 
    right = mid - 1; } }else{ 
   //如1,3,1,1,1寻找3, 对其进行捕捉,只能缩小边界值，改成right一样可以 if(nums[left] == target){ 
    return true; }else{ 
    left++; } /*if(nums[right] == target){ return true; }else{ right--; }*/ } } return false; } } 

L153

153. 寻找旋转排序数组中的最小值 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2] 输出: 1 示例 2:

输入: [4,5,6,7,0,1,2] 输出: 0

讯享网class Solution { 
    public int findMin(int[] nums) { 
    if(nums == null || nums.length == 0) return -1; int len = nums.length; int left = 0, right = len-1; while(left < right){ 
    int mid = left + (right - left)/2; if(nums[right] < nums[mid]){ 
    left = mid + 1;//只有在右边判断才是最有效的 }else{ 
    right = mid; } } return nums[left]; } } 

L154

154. 寻找旋转排序数组中的最小值 II 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5] 输出: 1 示例 2：

输入: [2,2,2,0,1] 输出: 0 说明：

这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

public class Solution { 
    public int findMin(int[] nums) { 
    int len = nums.length; if (len == 0) { 
    return 0; } int left = 0; int right = len - 1; while(left< right){ 
    //int mid = left + (right - left)/2; int mid = (left + right) >>> 1; if(nums[mid] > nums[right]){ 
    left = mid+ 1; //比较只能和right比较，和left是无法得出结果的，对于1, 2, 3, 4, 5就不行 }else if(nums[mid] < nums[right]){ 
    right = mid; }else{ 
    right--; //此时left恰好为最小值的位置，移动right则不会有任何问题，反正mid与它相同,移动left就会出错 } } return nums[left]; } } 

L275

275. H指数 II
     给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。编写一个方法，计算出研究者的 h 指数。

示例:

输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了
0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

题意有点不容易理解，但是其实是类似的，就是找到一个位置，对应为>=某一个指数的第一个位置，同时要满足该位置，剩下的长度要小于等于该值，即cita[mid] >= len - mid

讯享网class Solution { 
    public int hIndex(int[] cita) { 
    int len = cita.length; if(len == 0) return 0; if(cita[len -1]== 0) return 0;//最大值为0也是不满足的，若只有0一个元素，下面是无法判断的 //实际这个题是寻找第一个大于等于某个值的位置 int left= 0, right = len - 1; while(left < right){ 
    int mid = left + (right - left)/2; if(cita[mid] >= len - mid){ 
    //看 nums[mid] 和区间 [mid, len - 1] 的长度，即 len - 1 - mid + 1 = len - mid right = mid; }else{ 
    left = mid + 1; } } return len - left; } }