leetcode-33. Search in Rotated Sorted Array

本文主要是介绍leetcode-33. Search in Rotated Sorted Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode-33. 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.

这里基本思想就是二分法，而二分法其实并不需要严格排序，比如这一题，由于是Rotated，所以如果将数组二分的话至少会有一半是严格二分的，又因为不存在重复元素，我们只要判断严格递增区域的是否包含target就好了。如果严格递增区域没有则必定在另一半。

当然corner case还是有点麻烦的。。需要认真判断一下。这里有数个需要判断是否加等号的不等式判断，需要非常注意。

另外如果这题元素不是严格递增的，那么就是另一个问题了这种解法是不可行的。怎么做还需要再思考。

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

这篇关于leetcode-33. Search in Rotated Sorted Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---