current position:Home>33. Search rotation sorting array (c + + problem solution, including vs runnable source program)

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. 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;
}

copyright notice
author[Bufan],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270437276045.html

Random recommended