注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex33 Search in Rotated Sorted Array  

2015-05-16 21:25:28|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个题上午做的时候,直接用的线性查找,貌似oj也上让过了。

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

我觉着是不是太容易了,后来网上搜了一下信息,惊呆了,要用二分查找。而且这个关于下标的判定特别恶心,现在又糊涂了。

int search(int* nums, int numsSize, int target){
int left, right,mid;
left = 0;
right = numsSize - 1;
//这一题的二分搜索下标界线判定太难了,需要仔细考虑
while (left <= right)
{
mid = left + (right - left) / 2;
if (target == nums[mid])
return mid;
if (nums[left]<nums[mid])
{
// 说明落在第一个上升区间
if (nums[left]<=target&&target < nums[mid])
{
//在left 和mid-1的区间搜索
right = mid - 1;
}
else
{
left = mid + 1;
}
}
else if (nums[left]>nums[mid])
{
//说明落在第二个上升区间
if (nums[mid]<target&&target <= nums[right])
{
//在left 和mid-1的区间搜索
left = mid + 1;
}
else
{
right = mid - 1;
}
}
else //单独考虑 left和mid重合的情况
{
left = mid + 1;
}
}

return -1;

}

这个题以后还应该研究一下,特别经典。网上有个方法挺不错的,但是貌似代码有点儿问题,我加了一个分支。
http://www.cnblogs.com/lichen782/p/leetcode_Search_in_Rotated_Sorted_Array.html
  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017