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

直接遍历：

public int search (int[] nums, int target) {
    for (int i=0;i<nums.length;i++){
        if(target == nums[i]) return i;
    }
    return -1;
}

运行时间：32ms
超过55.72% 用Java提交的代码
占用内存：12260KB
超过37.98%用Java提交的代码

二分查找，略微优化版本：

public int search(int[] nums, int target) {
    if(nums == null || nums.length == 0) return -1;
    if(nums.length == 1) {
        if(nums[0] == target) return 0;
        else return -1;
    }else {
        int pos = 0;  // 查找位置
        for (; pos < nums.length - 1; pos++) {
            if (target == nums[pos]) return pos;
            if (nums[pos] > nums[pos + 1]) break;
        }
        int resu1 = binarySearch(nums, 0, pos, target);
        int resu2 = binarySearch(nums, pos + 1, nums.length - 1, target);
        return resu1 == -1 ? resu2 : resu1;
    }
}

private int binarySearch(int[] nums, int left, int right, int target) {
    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] > target) right = mid - 1;
        else if(nums[mid] < target) left = mid + 1;
        else{
            return mid;
        }
    }
    return -1;
}

运行时间：36ms
超过17.15% 用Java提交的代码
占用内存：12128KB
超过69.17%用Java提交的代码