题目

• 整数数组 nums 按升序排列，数组中的值互不相同 。
• 在传递给函数之前，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 。

LeetCode链接

题解

• 旋转排序后的数组可以视为两个单调递增的序列，可依据left、mid、right三个值判断当前部分序列是否为单调递增序列；
• 若nums[mid]==target，则直接返回mid；
• 若nums[left]<nums[mid]，则至少说明从left到mid这段序列是递增的。进而，如果nums[left]<=target&&target<nums[mid]，那么target必定在left到mid-1这段区间中；反之，target在mid+1到right这段区间中；
• 若nums[left]>nums[mid]，那么从mid到right这段序列是递增的（只存在两段递增序列）。进而，如果nums[mid]<target&&target<=nums[right]，那么target必定在mid+1到right这段区间中；反之，target在left到mid-1这段区间中。

源码

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;
}
复制代码