1. Answer key

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[0]) {
    
			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[0]) {
    
			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;
}