题解 | #在旋转过的有序数组中寻找目标值#

import java.util.*;
//方发1：暴力解法。时间复杂度：O(n)
//方法二：二分法。时间复杂度：O(logn)
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        
//         int length = nums.length;
//         //方发1：暴力解法。一次遍历。时间复杂度：O(n)
//         for(int i=0;i<length;i++){
//             if(target == nums[i]){
//                 return i;
//             }
//         }
        
//         return -1;
        
        //方法二：二分法。
        int length = nums.length;
        //特殊值处理,此时长度小，可以不用进入循环，提高效率
        if(length == 1){
            return nums[0]==target?0:-1;
        }
        //目标值比第一个值nums[0]小，而且比最后一个值nums[length-1]大，eg：[6,8,10,0,2,4],目标值为5
        if(nums[0]>target && nums[length-1]<target){
            return -1;
        }
        
        int minValue = nums[0];//临时最小值（minValue） 
        int min = 1;//二分法，左指针
        int max = length-1;//二分法，右指针
        int mid = (min+max)/2;//二分法，中值
        while(min <= max){//结束循环条件：最小值大于最大值
            if(nums[mid] == target){//中值与临时最小值相等
                return mid;
            }else if(nums[mid] > minValue){//中值大于临时最小值（minValue），此时左边是严格升序的，由中值划分出两个区间
                //如果目标值小于中值（在左边是最大值），且大于或等于最小值，此时目标值如果存在，则一定在此期间内，不可能在右边
                if(target<nums[mid] && target>=nums[min]){
                    max = mid -1;
                }else{
                    min = mid + 1;
                }
            }else {//中值小于临时最小值（minValue），此时右边是严格升序的
                //如果目标值大于中值（在右边是最小值），且小于或等于最大值，此时目标值如果存在，则一定在此期间内，不可能在左边
                if(target>nums[mid] && target<=nums[max]){
                    min = mid + 1;
                }else{
                    max = mid - 1;
                }
            }
            mid = (min+max)/2;//求中值
        }
        
        return -1;//循环结束，min>max，不存在目标值
    }
}