# 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```

``` Share my intuitive thinking: the main idea is that we need to find some parts of array
that we could adopt binary search on that, which means we need to find some completed
sorted parts, then determine whether target is in left part or right part. There is at
least one segment (left part or right part) is monotonically increasing.```

## 解法：

```    public int search(int[] nums, int target) {
if (nums == null || nums.length ==0) return -1;
int left = 0 ,right = nums.length-1,mid;
while (left<=right){
mid = left+(right-left)/2;
if (nums[mid] == target ) return mid;
if (nums[left] <= nums[mid]){
//left to mid is monotonically increasing
if (target < nums[mid] && target>=nums[left]){
right = mid-1;
}else {
left = mid+1;
}
}else {
//mid to right is monotonically increasing
if (target<=nums[right]&& target>nums[mid]){
left = mid+1;
}else {
right = mid-1;
}
}
}
return  -1;
}```

# 81.Search in Rotated Sorted Array II

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

(i.e., `[0,0,1,2,2,5,6]` might become `[2,5,6,0,0,1,2]`).

You are given a target value to search. If found in the array return `true`, otherwise return `false`.

Example 1:

```Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true```

Example 2:

```Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false```

`while(left < right && nums[left]== nums[right]) left++;`

## 解法：

```public boolean search (int[] nums, int target) {
if (nums == null || nums.length ==0) return false;
int left = 0 ,right = nums.length-1,mid;
while (left<=right) {
while (left < right && nums[left] == nums[right]) left++;
mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
if (nums[left]<=nums[mid]){
if (target>=nums[left]&&target<nums[mid]){
right = mid-1;
}else left = mid+1;
}else {
if (target>nums[mid]&&target<=nums[right]){
left = mid+1;
}else right = mid-1;
}
}
return false;
}```

0 条评论

## 相关文章

2468

### Python变量与数据类型

1 Python中数据类型 1、整数 Python可以处理任意大小的整数，当然包括负整数，在Python程序中，整数的表示方法和数学上的写法一模一样，例如：，，...

2806

3693

### 1245 最小的N个和

1245 最小的N个和 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...

2745

2037

3878

3714

1123

3984