leetcode: Search in Rotated Sorted Array

问题描述：

Suppose a sorted array 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.

原问题链接：https://leetcode.com/problems/search-in-rotated-sorted-array/

 

问题分析

　　这个问题在之前的文章里有讨论过。总的来说是基于这么一个思路。当我们将一个排序后的数组循环移位之后，其实它就构成了两个递增的段。我们用二分查找法去查找元素的时候。如果nums[mid] < nums[r]，则表示它的中间节点落在后面的这个递增的段上。否则如果nums[mid] > nums[l]，则可以表示成它的中间节点落在前面的这个递增段上。这个时候我们就需要对要查找的目标值和它们进行比较。

　　假设中间节点落在后续的递增段上，那么如果目标值target > nums[mid] 而且target < nums[r]，则表示要查找的值在mid的右边，否则它就在mid的左边。对于中间点落在前面的递增段上的情况类似，如果target > nums[l] && target < nums[mid]，它肯定是落在mid前面部分，否则就应该在mid后面查找。

 

public class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return -1;
        int l = 0, r = nums.length - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] <= nums[r]) {
                if(target > nums[mid] && target <= nums[r]) l = mid + 1;
                else r = mid - 1;
            } else {
                if(target < nums[mid] && target >= nums[l]) r = mid - 1;
                else l = mid + 1;
            }
        }
        return -1;
    }
}

   按照这种方式可以得到元素结果的值。其算法的时间复杂度为O(logN)。

 

参考材料

http://shmilyaw-hotmail-com.iteye.com/blog/1626910