The title

• The integer array NUMs is sorted in ascending order, with different values in the array.
• Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].
• Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.

LeetCode link

Answer key

• The array sorted by rotation can be regarded as two monotonically increasing sequences. The left, mid and right values can be used to determine whether the current partial sequence is monotonically increasing.
• If nums[mid]==target, return mid;
• If nums[left]
• If nums[left]>nums[mid], then the sequence from mid to right is increasing (there are only two increasing sequences). If nums[mid]

The source code

int search(int* nums, int numsSize, int target)
{
	int left = 0;
	int right = numsSize - 1;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] == target)
		{
			return mid;
		}
		if (nums[left] <= nums[mid])
		{
			if (nums[left] <= target && target < nums[mid])
			{
				right = mid - 1;
			}
			else
			{
				left = mid + 1; }}else
		{
			if (nums[mid] < target && target <= nums[right])
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1; }}}return - 1;
}
Copy the code