首页 > 代码库 > 【优化王牌】二分查找
【优化王牌】二分查找
二分查找
二分法?多简单?NO!NO!NO!我们可不是讲俗透顶的二分查找!我们讲的是二分查找的应用!
我们讲的也不是二分答案,是优化。
你真的会充分地用二分查找吗?
事实告诉你:含序列题目并可以暴力等求出答案的,基本上二分查找都是可以将其优化的!
不信?咱们来看看一道简单的排序:
MZA 的排序
【问题描述】
现在知道 MZA 有一堆同学,也不知道有多少个。
可恶的 MZA 现在给了你这堆同学的名字和成绩(都是英文名字),请你输出他们的成绩排序。每个人一行,先输出名字,然后输出成绩。
然后 MZA 就不乐意了。
【输入格式】
每行先是名字,然后是分数
数据以“end -100"结尾
【输出格式】
每行先是名字,然后是分数
【输入样例】
WXJ 99THC 20YSM 100SWQ 50CC 59LJX 10YSF 0end -100
【输出样例】
YSM 100WXJ 99CC 59SWQ 50THC 20LJX 10YSF 0
【数据规模与约定】
保证名字不超过 100个字符。
成绩都是不超过 100 的正整数。
保证不超过 1000 个同学
数据保证没有人分数相同
【试题分析】
这么简单!直接冒泡O(n^2)不就得啦!
但要是数据范围大一点或时间少一点不就完了吗?而且冒泡排序交换时还需要O(len)来复制呢~~
所以要想在上面前提下AC,我们就可以用到二分查找。
怎么找呢?
1.把输入的序列存两个数组。
2.把A数组排序(随便你用sort,qsort,mergesort……只要别用冒泡就行了)
3.每次都找b[0~n-1]在现在的A数组里面的下标。
4.找到下标以后,直接复制给anschar相应下标即可
5.直接输出
有没有发现,找下标时总可以用到二分法优化一下。
所以优化后的复杂度为O(nlogn)
【代码】
#include<iostream>#include<algorithm>#include<cstring>using namespace std;int a[1001],b[1001];char anschar[1001][110],in[1001][110];int bsearch(int x,int n){ int left=0,right=n-1; while(left<=right) { int mid=(left+right)/2; if(a[mid]==x) return mid; else if(a[mid]>x) left=mid+1;//因为我们是从大往小排,所以切记不要忘了该符号 else right=mid-1; } return -1;}bool cmp(int a,int b){ return a>b;}int main(){ int i=0; while(cin>>in[i]>>a[i]&&a[i]!=-100&&strcmp(in[i],"end")!=0) b[i]=a[i],i++; sort(a,a+i,cmp);//从大往小排 for(int j=0;j<i;j++) { int tmp=bsearch(b[j],i);//找原来输入的每个数在A数组里的下标 strcpy(anschar[tmp],in[j]);//直接复制 } for(int j=0;j<i;j++) cout<<anschar[j]<<" "<<a[j]<<endl;//直接输出}
这就是优化的思想,也是非常有用的一类思想。
大家还可以看这道题:
http://www.cnblogs.com/wxjor/p/5793222.html
【优化王牌】二分查找