判断数字是否在循环移位的数组中
给定一个数组，此数组是由数组进行循环移位后得到的，判断目标数字是否在循环数组中。例如：给定A=[6,7,8,1,2,3,4,5]此数组是由数组B=[1,2,3,4,5,6,7,8]进行循环移位后得到的，给定目标数字target判断是否在数组A中。要求时间复杂度为O(logn)
解析：循环移位后的数组分为两部分，是部分有序的，并且要求时间复杂度为O(logn)，因为可以考虑变种的二分查找。分别定义low,high,mid，下面分情况讨论。
[cc lang=”C++”]
if nums[mid] === target 直接返回
else if nums[mid] target)//目标数值在mid右侧
low = mid+1
else if (nums[high] < target)//target =7时， 目标数值在mid左侧 high= mid -1 else //nums[mid] > target
//以数组[4,5,6,1,2,3,4]为例，nums[mid]=7 此时需要比较nums[low]和target之间的相互关系
if (nums[low] > target) // target =1 说明target在mid的右半边
low = mid +1
else if (nums[low] < target) //target=6 说明target在mid的左半边 high = mid -1 [/cc] 来看代码： [cc lang=”C++”] int binary_search(vector nums, int target)
{
int low = 0;
int high = nums.size()-1;
while(low <= high) { int mid = (low + high) /2; cout << “low:” << low << “,high:” << high << “,mid:” << mid << endl; if(nums[mid] == target) return mid; else if(nums[mid] < target) { if(nums[high] == target) return high; else if(nums[high] > target)
low = mid +1;
else
high = mid -1;
}else
{
if(nums[low] == target)
return low;
else if(nums[low] > target)
low = mid +1;
else
high = mid -1;
}
}
return -1;
}
[/cc]
About Author
