算法第二章上机实践报告
1.实践题目
改写二分搜索算法
2.问题描述
设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
输入有两行：
第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。
输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时，i和j相同。 提示：若x小于全部数值，则输出：-1 0 若x大于全部数值，则输出：n-1的值 n的值。
算法描述：
#include<iostream>using namespace std;
const int MAXSIZE = 100000;
int main() {// int s1[MAXSIZE], S2[MAXSIZE], n; int n; cin >> n; int s1[n], s2[n]; for(int i = 0; i < n; i++) cin >> s1[i]; for(int j = 0; j < n; j++) cin >> s2[j];
int s[2 * n]; int index1 = 0, index2 = 0; for(int k = 0; k < 2 * n; k++) if(s1[index1] > s2[index2]) { s[k] = s2[index2]; index2++; } else { s[k] = s1[index1]; index1++; } cout << s[n - 1]; return 0;}
其它思路：
（没有用到二分法）
#include<iostream> using namespace std; int main() { //shuru int n; cin>>n; int x; cin>>x; int a[n]; int i,k,t,y; for(i=0;i<n;i++) cin>>a[i]; //zhao x wei zhi if(x>a[n-1]) cout<<n-1<<" "<<n; if(x<a[0]) cout<<-1<<" "<<0; else { for(t=0;t<n;t++) if(x==a[t]) cout<<t<<" "<<t; //ke yi jie shu for(k=0;k<n;k++) { if( (a[k]<x)&&(x<a[k+1]) ) cout<<k<<" "<<k+1; } } }
转载于:https://www.cnblogs.com/smclrh35665632/p/11567677.html
相关资源：数据结构与算法分析Java语言描述第二版 课后习题答案