|
leetcode no.33 搜索旋转排序数组 二分问题，注意边界和只有两个的考虑情况。 因为mid是起到向下取整的效果，因此要考虑好a[left]=a[mid]的情况 退出的条件为a[mid]==target或者l>r 对较大的部分的定义 4 5 6 7 1 2 3 此时4 5 6 7是较大的部分，判断mid所处单元用其与left处关系对比判断哦 大范围先判断mid和target的关系，进入分支以后确定mid是在较大还是正常部分 a[mid]>target时，可能出现的情况：a[mid]在较大的那部分,那么说明前面都比a[mid]小，（此时若a[left]<=target），那么结果一定在[left,mid]中，注意带等号，不然就空掉了left处正好是target，反之，如果a[left]>target，那么结果一定在右半部分。而如果a[mid]在较小的部分，还是比target大，那么只有其左侧的部分才有可能。（7 1 2 3 4 5 6）这种序列 a[mid]<target的时候，如果mid在较小的单元，那么可能在左侧的较大部分出现，也可能在右侧正常递增中出现，如果a[right]>=target，一定会出现在右侧。如果mid在较大单元，那么一定是在其右侧出现。 值得注意的是，因为每次在知道mid与target的关系后，都要先判断mid是在较大部分还是较小部分，而mid的产生是先根据(left right)/2产生的，那么他向下取整就有可能会触碰到a[left]==a[mid]的情况，因此，在判断较大较小时a[left]<=a[mid]是带等号的，右边就不需要（因为右边如果出现相等，那一定是left和right同，只有一个元素的）
 class Solution {
public:
int search(vector<int>& nums, int target) {
int len=nums.size();
int l,r,mid;
l=0;
r=len-1;
mid=(l r)/2;
while(l<=r)
{
//printf("%d %d\n",l,r);
if(nums[mid]==target)
return mid;
if(nums[mid]>target)
{
//printf("hah1");
if(nums[l]<=nums[mid])//4 5 6 7 1 2 3
{
//printf("hah2");
if(nums[l]<=target)
r=mid-1;
else
l=mid 1;
}
else
r=mid-1;
}
else//nums[mid]<target
{
if(nums[l]<nums[mid])
l=mid 1;
else
{
if(nums[r]>=target)
{
l=mid 1;
}
else
r=mid-1;
}
}
mid=(l r)/2;
}
return -1;
}
};View Code来源：https://www./content-4-725201.html
|
