梁其星 20181003115 软工1803
一. 实践题目
7-2 改写二分搜索算法 (20 分)
输入格式:
输入有两行：
第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。
输出格式:
输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时，i和j相同。 提示：若x小于全部数值，则输出：-1 0 若x大于全部数值，则输出：n-1的值 n的值
输入样例:
6 5
2 4 6 8 10 12
输出样例:
1 2
二.问题描述
题目来源：《计算机算法设计与分析》，王晓东
设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
三. 算法描述
1）#include <iostream>
2）using namespace std;
3）int binary(int a[],int n, int x)
4）{
5） int i=-1;
6） int j=0;
7） int temp=-1;
8） int left=0;
9） int right=n-1;
10） int mid=0;
11） while(left<=right)
12） {
13） mid=(left+right)/2;
14） if(a[mid]==x)
15） {
16） temp=mid;
17） }
18） if(a[mid]<x)
19） {
20） left=mid+1;
21） }
22） else
23） {
24） right=mid-1;
25） }
26） }
27）
28） if(temp!=mid)//x不在数组中
29） {
30） i=right;
31） j=left;
32） }
33） else
34） {
35） i=temp;
36） j=i;
37） }
38） cout<<i<<" "<<j;
39） return 0;
40）}
41）
42）
43）int main()
44）{
45） int a[100];
46） int b[100];
47） int n,x;
48） cin>>n>>x;
49） for(int k=0;k<n;k++)
50） {
51） cin>>a[k];
52） }
53） binary(a,n,x);
54） return 0;
分析：
①binary（）函数与7-1方法一致，都是二分查找的步骤。在第28行开始利用临时变量temp来确定x是否为数组中的元素，若不是，则i，j不等且为临近的两个下标，若相等则把temp的值赋给i和j；
②因题目要求x小于全部值时输出的i，j值为-1和0，故此处我将i的初值赋值为-1便于我后续的输出
四.算法时间及空间复杂度分析
将数组分为两部分，每次执行，数组规模减半，利用a[mid]与要寻找的x做比较，再确定x在哪半部分，故时间复杂度为O（log n）
非递归的二分查找，故空间复杂度为O（1）
五.心得体会
此题在考虑特殊情况时做的不好，如x小于所有元素时的情况没有考虑到，i和j的初值赋得不好，程序的健壮性不足；
另一方面一开始读题的时候没有读仔细，以为输入的数组只要求非降序，故还多考虑了将输入的数组排序后再进行二分算法，实际上输入的数组就是升序的，故一开始的排序函数是冗余的；
二分算法的递归做法还不熟练，本题我用的是非递归的算法，这方面的知识需要加强。