题解——冒泡+二分查找 _题解

男儿欲遂平生志，六经勤向窗前读。这篇文章主要讲述题解——冒泡+二分查找相关的知识，希望能为你提供帮助。

题解——冒泡+二分查找

文章目录

??题解——冒泡+二分查找??
??题面??
- - ??描述??
  - ??输入??
  - ??输出??
  - ??样例输入??
  - ??样例输出??
  - ??提示??
??题解??
- ??冒泡排序??
- - ??升序??
  - ??降序??
- ??二分查找??
- - ??二分查找——升序??
  - ??二分查找——降序??
- ??输入??
- - ??AC做法??
  - ??原理??

题目链接：?

??传送门??
题面描述有一组数据放在数组??R[ ]???中，??R[ ]=9,8,7,6,0,-1,10,-5,-32,66???，请调用冒泡排序函数（自己定义函数），先将数组进行排序，然后调用二分查找算法（自己定义函数）查找某数，分别给出比较次数，每个比较次数占一行，比较次数为??-1??时表示没找到。
输入第1行输入排序标志，为??1??时，对原数组先采用升序排序，为??2??时，对原数组采用降序排序。
第2行开始输入待查找的数。输入??非整数???或??^Z??时，结束输入。
输出采用二分查找法查找某数时的比较次数，每个比较次数占一行，比较次数为??-1??时表示没找到。
样例输入

1
-1
25
6

样例输出

3
-1
1

提示直接在程序里定义??R[ ]=9,8,7,6,0,-1,10,-5,-32,66??
ps. 这里有点狠！让你直接在程序里定义，结果原题混入一个中文逗号！

文章图片

题解这个题对大家来说陌生的地方可能主要在于输入要求：

输入非整数或^Z时，结束输入。

??^Z???其实是??ctrl+Z??的意思，这是一个文件结束符，当你在键盘上敲??ctrl+Z??的时候，相当于输入了“文件结束符”，你的程序必须能读取“文件结束符”，并使输入停止。
我们一步一步来：
首先按题意，定义数组??r??

#include < iostream>
using namespace std;
int r[]=9,8,7,6,0,-1,10,-5,-32,66;

ps. 为了方便使用，我们直接把它定义为全局变量
冒泡排序
升序

void cin_up()
int t;
for(int i=0; i< 10; i++)
for(int j=0; j< 9; j++)
if(r[j]> r[j+1]) //升序
t=r[j],r[j]=r[j+1],r[j+1]=t;

降序

void cin_down()
int t;
for(int i=0; i< 10; i++)
for(int j=0; j< 9; j++)
if(r[j]< r[j+1]) //降序
t=r[j],r[j]=r[j+1],r[j+1]=t;

二分查找
首先需要注意的一点是，二分算法可能需要根据序列的增减性不同而作出相应调整，如：

若待查找序列为升序，如??0 1 2 3 4 5 6??，要找??5??，第一次??mid=(0+6)/2=3??，??r[mid]=3< 5??，此时应该进行的操作是??l=mid+1??；
若待查找序列为降序，如??6 5 4 3 2 1 0??，还是要找??5??，第一次??r[mid]=3< 5??，此时进行的操作就不是??l=mid+1??了，而是??r=mid-1??；

因此，我们干脆就写两个二分查找函数，根据升序/降序的不同选择性地调用它们即可。
二分查找——升序

int binFind_up(int key)
int L=0,R=9,mid,num=0;
while (L< =R)
num++;
mid=(L+R)/2;
if(r[mid]==key)return num;
else if(r[mid]< key)
L=mid+1;
else
R=mid-1;

return -1;

二分查找——降序

int binFind_down(int key)
int L=0,R=9,mid,num=0;
while (L< =R)
num++;
mid=(L+R)/2;
if(r[mid]==key)return num;
else if(r[mid]> key)
L=mid+1;
else
R=mid-1;

return -1;

输入
AC做法

int main()
int n; // 排序标志n
cin> > n;
if(n==1)
cin_up(); // 采用升序排序
else if(n==2)
cin_down(); // 采用降序排序
int x;
while (cin> > x) // 符合要求的数据输入方法
if(n==1)cout< < binFind_up(x)< < endl;
else cout< < binFind_down(x)< < endl;

return 0;