文章目录
闫而总之，只要所要寻找的数组能够满足某一条件而被分成两边，就能进行二分，这边我们就拿有序数组的二分来做例子；
假设目前有这么一组数据:1 2 2 3 3 4 下标从0开始
假设此时的情景为，需要我们找到第一个>=3的数字，试想一下，如果能把整个区间分了两半，左边是<3的区间，右边是>=3的区间 如图:
那么右区间的第一个点，就是我们找到的符合>=3的第一个数字,将区间分为两半，是不是非常清晰！
我先给出代码实现(不要害怕 马上就能见证奇迹)
#include<iostream>
using namespace std;
int main()
{
int a[6]={1,2,2,3,3,4};
int l=-1,r=6;//定义两个指针
while(l+1!=r)
{
int mid=l+r>>1;//(相当于(l+r)/2)
if(a[mid]<3) l=mid;//或者if(a[mid]>=3) r=mid;
else r=mid; // else l=mid;
}
cout<<"第一个3所在的下标为 "<<r<<endl;
return 0;
}
返回的结果为:第一个3所在的下标为 3
最后二分的结果就是下面这个图，是我们想要的样子！
然后因为我们要找到的是第一个>=3的数字，所以就取 r 也就是>=3区间的第一个数字；
对于一个有序数组,假设下标为0,1,2,3…,n-1;总共n个数字
那么模板为
int L=-1,R=n;
while(L+1!=R)
{
int mid=L+R>>1;
if(check()) L=mid;
else R=mid;
//最后根据你所分左右两边区间的结果
//选取L或者R作为结果
}
首先，如果二分本来就没有结果
比如对于本文例题 1 2 2 3 3 4，，如果你要寻找第一个 >=5 的数，你会发现，整个过程都在执行L=mid，最后得到的结果中,R是等于下标6的，他明显这个时候是越界的，说明我们找不到要寻找的数字，而如果我们一开始将R赋值为n-1，也就是赋值为下标5的时候，他返回的R是5，是没有越界的，被我们当成了答案，但其实这时候我们的二分是没有答案的,就发生了错误；
其次，L最小值为-1，R最小值只能取到1，因为L+1！=R为循环结束条件，R最大值为N,同理则L的最大值为N-2，则（L+R）/2的取值范围是 [0,N)
mid的值始终位于0到N的左闭右开区间里面,不会发生越界的错误；
之前学过二分的小伙伴可能会发现，之前学的二分，他循环结束的条件是while(L<R)
而这边给出的循环条件是while(L+1!=R) 其实，就是当L和R相邻的时候，循环就结束，而原本的while(L<R)
是当两区间重合以后，循环才结束，所以之前我们需要判断对mid进行加一或者减一的操作，而且因为区间重合的问题，最后返回的L、R还要再进行判断，而这边的这个二分，因为区间反回的是不重合的两区间，只有L=mid和R=mid这两种情况，最后根据需要返回L或者R；
对于比较奇葩的情况，比如数组大小为1或者2
比如int a[1],b[2];
由于我们是while(L+1!=R)结束循环，也就是当L和R相邻的时候结束条件
对于a[1],他的下标为0 此时L=-1，R=n也就是1
对于b[2],他的下标为0,1 此时L=-1，R=n也就是2
所以无论何种情况，初始的L+1始终小于R，历经循环后最终L和R相邻，不会出现一开始L就和R重合等情况导致出现while(L+1!=R)循环不能结束的情况
我们就能够通过二分得到不重合的两区间，而且只需要L=mid和R=mid，不需要考虑L=mid+1，R=mid-1的情况
且记得一开始对于一个下标为0,1,2…n-1的数组，指针L要赋值为-1，指针R要赋值为n，那么你就学会了
最后我给出y总基础算法中的二分例题
数的范围的这题的关于这个二分方法的代码实现
数的范围
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,q[N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
while(m--)
{
int k;scanf("%d",&k);
//寻找第一个等于K的坐标 我这边让二分的边界定为 左边为<5 右边>=5 则所求为r
int l=-1,r=n;
while(l+1!=r)//当l与r没有相接的时候,求边界
{
int mid=l+r>>1;
//下面找第一个>=5的坐标
if(q[mid]>=k) r=mid;
else l=mid;
}
//此时得到的r是第一个>=5的坐标
if(q[r]!=k) printf("-1 -1\n");
else{
printf("%d ",r);
//现在找最后一个<=5的数字 我这边让二分的左边为<=5 右边为>5 则所求为ll
int ll=-1,rr=n;
while(ll+1!=rr)
{
int mid=ll+rr>>1;
if(q[mid]<=k) ll=mid;
else rr=mid;
}
if(q[ll]!=k) printf("%d\n",r);
else printf("%d\n",ll);
}
}
}
当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案 没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。 关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/
我注意到像bundler这样的项目在每个specfile中执行requirespec_helper我还注意到rspec使用选项--require，它允许您在引导rspec时要求一个文件。您还可以将其添加到.rspec文件中，因此只要您运行不带参数的rspec就会添加它。使用上述方法有什么缺点可以解释为什么像bundler这样的项目选择在每个规范文件中都需要spec_helper吗？ 最佳答案 我不在Bundler上工作，所以我不能直接谈论他们的做法。并非所有项目都checkin.rspec文件。原因是这个文件，通常按照当前的惯例，只
我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121
我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or
我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s
这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Rubysyntaxquestion:Rational(a,b)andRational.new!(a,b)我正在阅读ruby镐书，我对创建有理数的语法感到困惑。Rational(3,4)*Rational(1,2)产生=>3/8为什么Rational不需要new方法(我还注意到例如我可以在没有new方法的情况下创建字符串)？
您认为可以作为插件很好地存在于您的Rails应用程序中必须实现的哪些行为？您过去曾搜索过哪些插件功能但找不到？哪些现有的Rails插件可以改进或扩展，如何改进或扩展？ 最佳答案 我希望在管理界面中看到一个引擎插件，它提供了应用程序中所有模型的仪表板摘要，以及可配置的事件图表。 关于ruby-on-rails-您希望看到哪些Rails插件？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questio
我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr
我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night
修改(澄清问题)我已经花了几天时间试图弄清楚如何从Facebook游戏中抓取特定信息；但是，我遇到了一堵又一堵砖墙。据我所知，主要问题如下。我可以使用Chrome的检查元素工具手动查找我需要的html-它似乎位于iframe中。但是，当我尝试抓取该iframe时，它是空的(属性除外):如果我使用浏览器的“查看页面源代码”工具，这与我看到的输出相同。我不明白为什么我看不到iframe中的数据。答案不是它是由AJAX之后添加的。(我知道这既是因为“查看页面源代码”可以读取Ajax添加的数据，也是因为我有b/c我一直等到我可以看到数据页面之后才抓取它，但它仍然不存在)。发生这种情况是因为