# Search in Rotated Sorted Array I && II

`Leetcode`

### 对有序数组进行二分查找（下面仅以非递减数组为例）：

```
`int binarySort(int A[], int lo, int hi, int target)`
`{`
`    while(lo <= hi)`
`    {`
`        int mid = lo + (hi - lo)/2;`
`        if(A[mid] == target)`
`            return mid;`
`        if(A[mid] < target)`
`            lo = mid + 1;`
`        else`
`            hi = mid - 1;`
`    }`
`}`

```

### 对有序的旋转数组进行二分查找：

eg. [7, 8, 9, 3, 4, 5, 6]

1.如果前半部分有序：

• `target` 在该区间内，则 `hi = mid - 1`
• 不在该区间内，则 `lo = mid + 1`

2.如果前半部分无序

• `target` 在后半部分的有序区间内，则 `lo = mid + 1`
• 不在该区间内， 则 `hi = mid - 1`

```
`int search(int A[], int lo, int hi, int target)`
`{`
`    while (lo <= hi) `
`    {`
`        int mid = (lo + hi) / 2;`
`        if (A[mid] == target)`
`            return mid;`
`        if (A[lo] <= A[mid]) `
`        {`
`            if (A[lo] <= target && target < A[mid])`
`                hi = mid - 1;`
`            else`
`                lo = mid + 1;`
`        } else {`
`            if (A[mid] < target && target <= A[hi-1])`
`                lo = mid + 1;`
`            else`
`                hi = mid - 1;`
`              }`
`    }`
`    return -1;`
`}`

```

### 对包含重复元素的旋转数组进行二分查找:

• 若A[m]>A[l]，则区间[l,m]一定递增
• 若A[m]==A[l]确定不了，那就l++，往下看一步即可。
```
`bool search(int A[], int lo, int hi, int target)`
`{`
`    while (lo <= hi) `
`    {`
`        int mid = (lo + hi) / 2;`
`        if (A[mid] == target)`
`            return true;`
`        if (A[lo] < A[mid]) `
`        {`
`            if (A[lo] <= target && target < A[mid])`
`                hi = mid - 1;`
`            else`
`                lo = mid + 1;`
`        } else if(A[lo] > A[mid]) {`
`            if (A[mid] < target && target <= A[hi-1])`
`                lo = mid + 1;`
`            else`
`                hi = mid - 1;`
`              }`
`            else`
`                lo++;`
`    }`
`    return false;`
`}`

```

## LeetCode: Search in Rotated Sorted Array

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, othe

## Leetcode | Search in Rotated Sorted Array I &amp; II

Search in Rotated Sorted Array I 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 re

## LeetCode: Search in Rotated Sorted Array II 解题报告

Search in Rotated Sorted Array II Follow up for "LeetCode: Search in Rotated Sorted Array 解题报告":What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the arr

## LeetCode: Search in Rotated Sorted Array 解题报告

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 retu

## [LeetCode] Search in Rotated Sorted Array I (33) &amp;&amp; II (81) 解题思路

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