33 Search in Rotated Sorted Array

Leetcode

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

二分法。分两种情况。如果中间的元素在左边，若目标元素在左边且小于中间元素，右指针才移动，否则左指针移动。如果中间元素在右边，若目标元素在右边且大于中间元素，左指针才移动，否则有指针移动。

public int search(int[] nums, int target) {;
    boolean isLeft=target>=nums[0]?true:false;
    int l=0,r=nums.length-1;
    int t,mid;
    while(l<=r){
        mid=(l+r)/2;
        t=nums[mid];
        if(t==target) return mid;
        if(t>=nums[0]){
            if(isLeft && t>target){
                r=mid-1;
            } else {
                l=mid+1;
            }
        } else {
            if(!isLeft && t<target){
                l=mid+1;
            } else {
                r=mid-1;
            }
        }
    }
    return -1;
}