首页 > 代码库 > 【优化王牌】二分查找

【优化王牌】二分查找

二分查找

   二分法?多简单?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

【优化王牌】二分查找