# 33. Search rotation sorting array (c + + problem solution, including vs runnable source program)

2022-01-27 04:37:30 Bufan

### 33. Search rotation sort array （C++ Problem solution contains VS Can run the source program ）

1. First use the dichotomy idea to find the rotating subscript ;
2. Then use the dichotomy to find the target value .

explain ：

• As long as the time complexity is log（n） Lookup , Generally, you use two points to find the top. There must be nothing wrong , But the binary search array must be ordered ;
• Firstly, the idea of binary search is used to find the rotation position of the rotation array , In this way, the subarrays on both sides of this position are ordered ,
• Then judge whether to search for two points on the left or right according to the value of this position .

# 2. Power button C++ Source code

``````class Solution {

public:
int search(vector<int>& nums, int target) {

int left = 0;
int right = nums.size() - 1;
int mid = 0;
if (nums[left] <= nums[right]) {

return binsearch(nums, target, left, right);
}
while (left < right) {

mid = (left + right) / 2;
if (nums[mid] > nums[left]) {

left = mid;
}
else if (nums[mid] < nums[right]) {

right = mid;
}
if (right - left <= 1) {

break;
}
}
if (target >= nums) {

return binsearch(nums, target, 0, left);
}
else {

return binsearch(nums, target, right, nums.size() - 1);
}
}
int binsearch(vector<int>& nums, int target, int left, int right) {

int mid = 0;
while (left <= right) {

mid = (left + right) / 2;
if (nums[mid] < target) {

left = mid + 1;
}
else if (nums[mid] > target) {

right = mid - 1;
}
else {

return mid;
}
}
return -1;
}
};
``````

# 3.VS Can run the source program

``````#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<algorithm>
#include<math.h>
#pragma warning(disable:4996)
using namespace std;
// Firstly, the idea of binary search is used to find the rotation position of the rotation array , In this way, the subarrays on both sides of this position are ordered ,
// Then judge whether to search for two points on the left or right according to the value of this position .
class Solution {

public:
int search(vector<int>& nums, int target) {

int left = 0;
int right = nums.size() - 1;
int mid = 0;
// Array ascending , Directly call the dichotomy to return the result
if (nums[left] <= nums[right]) {

return binsearch(nums, target, left, right);
}
// Use dichotomy to find the rotating subscript
while (left < right) {

mid = (left + right) / 2;
if (nums[mid] > nums[left]) {

left = mid;
}
else if (nums[mid] < nums[right]) {

right = mid;
}
if (right - left <= 1) {

break;
}
}//right Subscript for rotation ,left Is the previous value of the rotation subscript ( Array maximum ) Subscript
// The target value is in the first half
if (target >= nums) {

return binsearch(nums, target, 0, left);
}
// The target value is in the second half
else {

return binsearch(nums, target, right, nums.size() - 1);
}
}
// Binary search
int binsearch(vector<int>& nums, int target, int left, int right) {

int mid = 0;
while (left <= right) {

mid = (left + right) / 2;
if (nums[mid] < target) {

left = mid + 1;
}
else if (nums[mid] > target) {

right = mid - 1;
}
else {

return mid;
}
}
return -1;
}
};
int main()
{

printf(" Input array size ：");
int n;
scanf("%d", &n);
printf(" Input array elements ：");
vector<int> nums;
int num;
for (int i = 0; i < n; i++) {

scanf("%d", &num);
nums.push_back(num);
}
printf(" Enter the target value ：");
int target;
scanf("%d", &target);
Solution test;
int res = test.search(nums, target);
printf(" The subscript of the target value is ：%d", res);

printf("\n");
system("pause");
return 0;
}
``````