《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告2

?

實(shí)驗(yàn)名稱: 可以進(jìn)行范圍查找的折半查找算法

系????別:xxx???????????

專????業(yè):xxx? ? ? ? ? ?

班????級(jí):xxx

姓????名:xxx? ? ? ? ??

學(xué)????號(hào):xxx

實(shí)驗(yàn)日期:xx年xx月xx日

?

1. ?算法題目

根據(jù)減治法的設(shè)計(jì)思想和算法步驟，要求學(xué)生設(shè)計(jì)一個(gè)減治算法，用于解決能夠進(jìn)行范圍查找的折 半查找算法的改造問(wèn)題。減治方法是分治方法中每次只走半邊區(qū)段的特殊分治法（既要么走左半 段，要么走右半段）。給定一個(gè)查找范圍(a,b)，可以分三種情況進(jìn)行處理。(a,b)段要么在左半段， 要么在右半段，要么跨兩半段。無(wú)論哪種情況，在下一輪迭代中只需要選擇一種情況進(jìn)行處理。因 此可以使用減治法解決該問(wèn)題。

?

2. ?設(shè)計(jì)思路與步驟

修改折半查找，分別用范圍的下限和上限與mid對(duì)比，if (l >= mid)，則改變查找下限；if (r <= mid)，則改變查找上限；否則就以mid為中心，向兩邊查找。

?

3. ?算法實(shí)現(xiàn)與代碼

#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("請(qǐng)輸入要查找的范圍：\n");

printf("l = ");

scanf("%d", &l);

printf("r = ");

scanf("%d", &r);

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

printf("輸入的范圍錯(cuò)誤！\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. ?測(cè)試用例與結(jié)果

?

5. ?問(wèn)題與總結(jié):

答：xxx。

?