# 力扣 leetcode 33. 搜索旋转排序数组()-其他

## 力扣 leetcode 33. 搜索旋转排序数组()

### 问题描述

``nums``

``k（0 <= k < nums.length）``
``[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]``
``0 ``
``[0,1,2,4,5,6,7]``
``3``
``[4,5,6,7,0,1,2]``

``nums``
``target``
``nums``
``target``
``-1``

``O(log n)``

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

### 示例 1：

``````输入：nums = [4,5,6,7,0,1,2], target = 0

``````

### 示例 2：

``````输入：nums = [4,5,6,7,0,1,2], target = 3

``````

### 示例 3：

``````输入：nums = [1], target = 0

``````

### 解题思路

``O(log n)``

``````class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0;
int high = nums.size();
int mid;
while(low < high){
mid = (low + high) / 2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] >= nums[low]){ // 左半部分有序
if(nums[mid] < target || target < nums[low]){ // 判断target是否可能出现在左边
low = mid + 1;
}
else{
high = mid;
}
}
else{ // 右半部分有序
if(nums[mid] < target && target < nums[low]){
low = mid + 1;
}
else{
high = mid;
}
}
}
return -1;
}
};
``````
————————

### 问题描述

``nums``

``k（0 <= k < nums.length）``
``[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]``
``0 ``
``[0,1,2,4,5,6,7]``
``3``
``[4,5,6,7,0,1,2]``

``nums``
``target``
``nums``
``target``
``-1``

``O(log n)``

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

### 示例 1：

``````输入：nums = [4,5,6,7,0,1,2], target = 0

``````

### 示例 2：

``````输入：nums = [4,5,6,7,0,1,2], target = 3

``````

### 示例 3：

``````输入：nums = [1], target = 0

``````

### 解题思路

``O(log n)``

``````class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0;
int high = nums.size();
int mid;
while(low < high){
mid = (low + high) / 2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] >= nums[low]){ // 左半部分有序
if(nums[mid] < target || target < nums[low]){ // 判断target是否可能出现在左边
low = mid + 1;
}
else{
high = mid;
}
}
else{ // 右半部分有序
if(nums[mid] < target && target < nums[low]){
low = mid + 1;
}
else{
high = mid;
}
}
}
return -1;
}
};
``````