4 折半查找 (10分)- 太简单

Dear 丶 2022-04-02 08:47 147阅读 0赞

折半查找的查找过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

每条待查记录包含关键字项和其他项，如关键字项为15，其他项为该记录在查找表里的原序号4。

对无序表的查找，还需要事先排列成有序表，再进行折半查找。

输入：

5 （记录的条数）

各记录项：如 32 1

输出：

已按关键字排列好的非递减序列：如 (16 2)(20 5)(32 1)(35 3)(91 4)

找不到时输出： error

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" rel="nofollow"><img alt="关于“测试输入”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" rel="nofollow"><img alt="关于“期待的输出”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“时间限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“内存限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" rel="nofollow"><img alt="关于“{$a} 个额外进程”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77932&amp;test=100751&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>11↵</li> 
     <li>5&nbsp;1↵</li> 
     <li>13&nbsp;2↵</li> 
     <li>19&nbsp;3↵</li> 
     <li>21&nbsp;4↵</li> 
     <li>37&nbsp;5↵</li> 
     <li>56&nbsp;6↵</li> 
     <li>64&nbsp;7↵</li> 
     <li>75&nbsp;8↵</li> 
     <li>80&nbsp;9↵</li> 
     <li>88&nbsp;10↵</li> 
     <li>92&nbsp;11↵</li> 
     <li>56↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77932&amp;test=100751&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>(5&nbsp;1)(13&nbsp;2)(19&nbsp;3)(21&nbsp;4)(37&nbsp;5)(56&nbsp;6)(64&nbsp;7)(75&nbsp;8)(80&nbsp;9)(88&nbsp;10)(92&nbsp;11)↵</li> 
     <li>(56&nbsp;6)↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>测试用例 3</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77932&amp;test=100753&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>10↵</li> 
     <li>5&nbsp;3↵</li> 
     <li>20&nbsp;4↵</li> 
     <li>100&nbsp;5↵</li> 
     <li>75&nbsp;6↵</li> 
     <li>63&nbsp;7↵</li> 
     <li>19&nbsp;8↵</li> 
     <li>18&nbsp;9↵</li> 
     <li>23&nbsp;10↵</li> 
     <li>32&nbsp;11↵</li> 
     <li>35&nbsp;12↵</li> 
     <li>36↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77932&amp;test=100753&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>(5&nbsp;3)(18&nbsp;9)(19&nbsp;8)(20&nbsp;4)(23&nbsp;10)(32&nbsp;11)(35&nbsp;12)(63&nbsp;7)(75&nbsp;6)(100&nbsp;5)↵</li> 
     <li>error↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td> <p>0</p> <p>&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

#include <stdio.h>
    #include <stdlib.h>
    typedef struct node{
            int x;
            int y;
    }NODE;
    
    int BubbleSort(NODE *list, int n)
    {
            int i,j,change;
            for (i = 1; i <= n; i++)
                    for (j=i;j<=n;j++){
                            if (list[j].x<list[i].x)
                            {
                                    change = list[i].x;
                                    list[i].x = list[j].x;
                                    list[j].x = change;
                                    change = list[i].y;
                                    list[i].y = list[j].y;
                                    list[j].y = change;
                            }
                    }
            return 1;
    }
    
    void Print(struct node *list,int n)
    {
            int i;
            for (i=1;i<n;i++)
            {
                    printf("(%d %d)",list[i].x,list[i].y);
            }
            printf("(%d %d)\n",list[n].x,list[n].y);
    }
    
    int Search(NODE *list, int n)
    {
            int head = 1 , tail = n , mid = (1 + n) / 2;
            while(head  <= tail)
            {
                    if (list[0].x == list[mid].x)
                    {
                            printf("(%d %d)\n",list[mid].x,list[mid].y);
                            return 1;
                    }
                    else if(list[0].x < list[mid].x)
                    {
                            tail = mid - 1;
                            mid = (head + tail) /2;
                            continue;
                    }
                    else
                    {
                            head = mid + 1;
                            mid = (head + tail) /2;
                            continue;
                    }
            }
            return 0;
    }
    int main(){
            int i,n,result;
            NODE list[200];
            scanf("%d",&n);
            for(i=1;i<=n;i++)
                    scanf("%d %d",&list[i].x,&list[i].y);
    
            scanf("%d",&list[0].x);    
            list[0].y = -1;
    
            if(BubbleSort(list,n))
                    Print(list, n); 
                      
            if(!Search(list, n))
                    printf("error\n");
    
            return 0;
    }