【leetcode每日刷題】33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 

[0,1,2,4,5,6,7]

 might become 

[4,5,6,7,0,1,2]

).

You are given a target value to search. If found in the array return its index, otherwise return 

-1

.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

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      

class num33 {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        if(target >= nums[0]){
            for(int i=0;i<nums.length&&nums[i]>=nums[0];i++){
                if(nums[i] == target) return i;
            }
        }else{
            for(int i=nums.length-1; i>=0&&nums[i]<=nums[nums.length-1]; i--){
                if(nums[i] == target) return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        num33 s = new num33();
        int[] nums = new int[]{1};
        int target = 2;
        System.out.println(s.search(nums, target));
    }
}
           

二分查找法

先判斷mid的位置，是處于前半段還是後半段，然後判斷mid相對于target的位置，使用二分查找的方法繼續查找。

public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = start + (end-start)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] >= nums[start]){
                if(target >= nums[start] && target < nums[mid]){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }else{
                if(target > nums[mid] && target <= nums[end]){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }
        }
        return -1;
    }