二分查找法，很经典的折半查找算法，想当然觉得很简单，算法效率log(2)N。今天跟它干上了，呵呵。真是实践出真知，不可想当然。
总结一下几个问题：
1、 习惯性思维中，二分查找算法用于查找一个升序（有序）数组，没问题；
int binary_search(int aa[],int n,int key)
{
int mid;
int low=0,high=n-1;
while(low<=high)
{
mid=low+((high-low)>>1);
if(key<aa[mid])
high=mid-1;
else if(key>aa[mid])
low=mid+1;
else return mid;
}
return -1;
}
2、 如果是一个降序数组呢。从大到小排序的。需要改变查找区间。将>改<，<改>
3、 Mid=(Low+high)/2，最好的写法应该是mid=low+(high-low)>>1;防止溢出并且移位效率更高；
4、 如果数组中有相等的元素呢？相等元素要么找出最小下标，要么找出最大下标？这个要做处理。
int binary_search(int aa[],int n,int key)
{
int mid;
int low=0,high=n-1;
while(low<=high)
{
mid=low+((high-low)>>1); //移位处理
if(key>aa[mid])
high=mid-1;
else if(key<aa[mid])
low=mid+1;
else
{
while(aa[--mid]==key) { //找最小小标
}
return mid+1;
}
}
return -1;
}
5、 最后给出一个应用题目。
小明同学是一名初一新生，校长听说他会C++编程，于是找到他，希望他能帮助学校编写一个程序。期中考试成绩出来了，很多同学想知道自己成绩排名的情况，只要考生输入自己的总分，就能快速知道自己在年级的排名情况及其同分数的人有多少？
输入格式：第1行一个数N（N<=10000）；第二行一个数K;第三行开始以N个以空格隔开的从高到低的所有学生中考成绩（整数）。接着K个待查找的考生成绩。
输出格式：K行，每行为一个待查找的考生的名次（不同分数的名次），同分数的人数，比考生分数高的人数。查找不到输出“fail！”。
输入样例：10
2
580 570 565 564 564 534 534 534 520 520
564 520
输出样例：
4 2 3
6 2 8
解答分析：该题是一个综合题，难点在于同分数出现次数，同分数名次相同，需要顺延名次。
#include<iostream>
#define N 100001
using namespace std;
int binary_search(int aa[],int n,int key)
{
int mid;
int low=0,high=n-1;
while(low<=high)
{
mid=low+((high-low)>>1); //移位处理
if(key>aa[mid])
high=mid-1;
else if(key<aa[mid])
low=mid+1;
else
{
while(aa[--mid]==key) { //找最小小标
}
return mid+1;
}
}
return -1;
}
int main()
{
int n,k;
int a[N];//定义a数组
int b[101],c[101]; //b数组代表要查找的好几个数；c数组存放在a中的位置
//pos数组三列，0列代表名次；1列代表同分数的人数；2列代表比考生分数搞的人数
int pos[101][3];
cin>>n; //输入n个数
cin>>k; //输入要查找的k个数
for(int i=0;i<n;i++)
cin>>a[i]; //输入
for(int i=0;i<k;i++)
cin>>b[i]; //输入要要查找的k个数
for(int i=0;i<n;i++)
{
int ans=0; //记录同分数段的人
//记录b[i]分数首次在a中出现的位置（最小下标）
int t=binary_search(a,n,a[i]);
pos[i][2]=t; //比该分数高的人数，即当前座次
//下面找同分数段的人数
while(a[t+1]==a[t])
{
ans++;
t++;
}
pos[i][1]=ans+1;
}
pos[0][0]=1;//第0个的排名为1
for(int i=0;i<n;i++) //如果累计分数段相同，排名不变
{
int temp=a[i];
for(int j=i;j<=i+1;j++) {
if(a[j]==temp)
pos[j][0]=pos[i][0];
else pos[j][0]=pos[i][0]+1;
}
}
for(int i=0;i<k;i++)
c[i]=binary_search(a,n,b[i]);
for(int i=0;i<k;i++)
{
if(!c[i]) {
cout<<"fail!";
break;
}
for(int j=0;j<3;j++)
cout<<pos[c[i]][j]<<' ';//输出查找的数的三列属性值
cout<<endl;
}
return 0;
}//该题也许用桶排序算法更简单。
网友评论