> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/33.-search-in-rotated-sorted-array.md).

# 33. Search in Rotated Sorted Array

https\://leetcode.com/problems/search-in-rotated-sorted-array/

无重复递增数组从某个点开始把后面元素全部按原来的序移到前面，找target所在位置，没有则返回-1。二分，根据nums\[mid]和nums\[0]以及target和nums\[mid]大小比较共有四种情况。先根据target和nums\[0]分成两种不以mid所在位置决定的静态情况。分别对这两种情况套用lower\_bound，考虑什么时候start 一定要前移到mid + 1：target >= nums\[0]时，mid落在\[nums\[0], target)；otherwise, mid落在\[target, nums\[0])外。

```
/*
 * @lc app=leetcode id=33 lang=cpp
 *
 * [33] Search in Rotated Sorted Array
 */

// @lc code=start
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int start = 0, end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (target >= nums[0]) {
                if (nums[mid] >= nums[0] && nums[mid] < target) start = mid + 1;
                else end = mid;
            } else {
                if (!(nums[mid] < nums[0] && nums[mid] >= target)) start = mid + 1;
                else end = mid;
            }
        } 
        return nums[start] == target ? start : -1; 
    }
};
// @lc code=end


```