《算法设计与分析》实验报告2

 

实验名称: 可以进行范围查找的折半查找算法

系    别:xxx           

专    业:xxx           

班    级:xxx

姓    名:xxx          

学    号:xxx

实验日期:xx年xx月xx日

 

1.  算法题目

根据减治法的设计思想和算法步骤，要求学生设计一个减治算法，用于解决能够进行范围查找的折 半查找算法的改造问题。减治方法是分治方法中每次只走半边区段的特殊分治法（既要么走左半 段，要么走右半段）。给定一个查找范围(a,b)，可以分三种情况进行处理。(a,b)段要么在左半段， 要么在右半段，要么跨两半段。无论哪种情况，在下一轮迭代中只需要选择一种情况进行处理。因 此可以使用减治法解决该问题。

 

2.  设计思路与步骤

修改折半查找，分别用范围的下限和上限与mid对比，if (l >= mid)，则改变查找下限；if (r <= mid)，则改变查找上限；否则就以mid为中心，向两边查找。

 

3.  算法实现与代码

#include<stdio.h>

#include<stdlib.h>

int Bisearch(int a[], int l, int r, int first, int end);

int main() {

int a[101], i, l, r;

for (i = 1; i < 100; i++) {

a[i] = i;

}

printf("请输入要查找的范围：\n");

printf("l = ");

scanf("%d", &l);

printf("r = ");

scanf("%d", &r);

if (l < 1 || r > 100 || l > r) {

printf("输入的范围错误！\n");

exit(0);

}

Bisearch(a, l, r, 1, 100);

return 0;

}

int Bisearch(int a[], int l, int r, int first, int end) {

int n = r - l;

int low = first, high = end;

int mid, flag, i;

while (low <= high) {

mid = (low + high) / 2;

if (l >= mid) {

low = mid - 1;

}

else if (r <= mid) {

high = mid;

}

else {

flag = 0;

i = mid;

while(!flag) {

if(a[i] == a[l]) {

flag = 1;

}

printf("%d ", a[i]);

i--;

}

flag = 0;

i = mid + 1;

while(!flag){

if(a[i] == a[r]) {

flag = 1;

}

printf("%d ", a[i]);

i++;

}

return 0;

}

}

return 1;

}

 

4.  测试用例与结果

 

5.  问题与总结:

答：xxx。