考研复试专用算法笔记（四）

落日映苍穹つ 2022-03-29 14:44 187阅读 0赞

四、查找

考虑时间复杂度是个让人头疼的问题，总结了一下，一般给出输入在1000以上的问题，都不建议 用冒泡，这里介绍个比较快的方法，二分查找。其重点有二：1，先排序 2，用中间数 把总数据个数分成两半。时间复杂度是O(nlogn(排序)+m\*logn)。

核心代码：

while(~scanf("%d",&n))\{

for(int i=0,i<n;i++) \{ scanf("%d",buf\[i\].no; \}

//第一步，排出序

sort(buf,buf+n);

//第二步，定义出头、尾、中间变量

int top=n-1,base=0;

char x\[30\];

scanf("%s",x);

while(top>base)\{

mid=(top+base)/2;

int tmp=strcmp(xx,xx)//这里写出要比较的东西

//第三步，二分比较（可以先看下面例题）

if(tmp==mid)\{ balabala...\}

else if(tmp>mid)\{ top=mid-1;\}

else\{base=mid+1;\}

例

给出一个数n表示接下来要输入n 组数据，再给出m表示想在这n组数中找到m组符合要求的数，再输入要求。

样例输入：

01 小张 男 12

02 小王 女 23

03 小李 男 11

样例输出：

03 小李 男 11

02 小王 女 23

参考：

\#include <stdio.h>  
\#include <algorithm>  
\#include <string.h>  
using namespace std;  
struct Student\{  
char no\[100\];  
char name\[100\];  
char sex\[30\];  
int age;  
bool operator <(const Student &A)const\{  
return strcmp(no,A.no)<0;  
\}  
\}buf\[1000\];  
int main()\{  
int n;  
while(~scanf("%d",&n))\{  
for (int i=0;i<n;i++)\{  
scanf("%s%s%s%d",buf\[i\].no,buf\[i\].name,buf\[i\].sex,&buf\[i\].age);  
\}  
sort(buf,buf+n);  
int t;  
scanf("%d",&t);  
while(t--!=0)\{  
int ans=-1;  
char x\[30\];  
scanf("%s",x);  
int top=n-1,base=0;  
while(top>=base)\{  
int mid=(top+base)/2;  
int tmp=strcmp(buf\[mid\].no,x);  
if(tmp==0)\{  
ans=mid;  
break;  
\}else if(tmp>0) top=mid-1;  
else base=mid+1;  
\}  
if(ans==-1)\{  
printf("No Answer!\\n");  
\}else printf("%s %s %s %d\\n",buf\[ans\].no,buf\[ans\].name,buf\[ans\].sex,buf\[ans\].age);  
\}  
\}  
return 0;  
\}

可能出错的点：

主函数里有两个while循环，大括号不要括错。

涉及数组的输入没有&号。

加油。