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

HT·生活

123

 
 
 

日志

 
 

ex153 Find Minimum in Rotated Sorted Array  

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

  下载LOFTER 我的照片书  |
开始没有抓住题目的要领。

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).

Find the minimum element.

You may assume no duplicate exists in the array.

题目要的实际上是一个logn的搜索算法,后来仔细一研究,原来是要用二分查找。关于二分查找这个算法,细想分析起来,简直是个大坑,特别容易犯错。二分搜索c代码

int binarySearch(int* nums, int numsSize)
{
//考虑一个复杂度为logn的算法 二分搜索
//对于二分搜索的话,如果nums是sorted过的话没有什么问题
//但是这里一个小问题就是它旋转了的
int target = 10;
int i;
int left, mid, right;
left = 0;
right = numsSize - 1;

while (left <= right)
{
mid = left + (right - left) / 2;
if (nums[mid] > target)
{
//
right = mid -1; //也剔除mid了
}
else if (nums[mid]<target)
{
left = mid+1; //已经剔除mid了
}
else
{
return mid;
}
}
return -2;
}

如网上一位网友的分析,特别要注意开区间和闭区间搜索的问题,不然越界或者陷入死循环了。
参考  http://blog.csdn.net/sunmenggmail/article/details/7540970里面给了一些关于二分常见错误的分析。

下面是我关于这个题的c代码,然后分析见下图。

ex153  Find Minimum in Rotated Sorted Array - HT - HT·生活
 

int findMin1(int* nums, int numsSize)
{
if (numsSize <= 0)
return 0;
int i, j;
int min = nums[0];
int low = 0, high = numsSize - 1,mid;
//这里选择的是闭区间
while (nums[low]>nums[high])
{
mid = low + (high - low) / 2;
if (nums[mid]>nums[high])
{
low = mid+1; //搜索 最小值不可能是mid下标的,
}
else if (nums[mid]<nums[high])
{
high = mid;
}
}
return nums[low]; //退出的时候肯定nums[low]<=mid[high]
}

后面还有关于这个二分搜索的变形,特别恶心。
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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