顺序表应用6：有序顺序表查询

「爱情、让人受尽委屈。」 2023-03-02 10:14 31阅读 0赞

## 顺序表应用6：有序顺序表查询 ##

Description  
顺序表内按照由小到大的次序存放着n个互不相同的整数，任意输入一个整数，判断该整数在顺序表中是否存在。如果在顺序表中存在该整数，输出其在表中的序号；否则输出“No Found!"。

Input  
第一行输入整数n (1 <= n <= 100000)，表示顺序表的元素个数；  
第二行依次输入n个各不相同的有序非负整数，代表表里的元素；  
第三行输入整数t (1 <= t <= 100000)，代表要查询的次数；  
第四行依次输入t个非负整数，代表每次要查询的数值。

保证所有输入的数都在 int 范围内。

Output  
输出t行，代表t次查询的结果，如果找到在本行输出该元素在表中的位置，否则本行输出No Found!

Sample  
Input  
10  
1 22 33 55 63 70 74 79 80 87  
4  
55 10 2 87  
Output  
4  
No Found!  
No Found!  
10

#include <stdio.h>
    #include <stdlib.h>
    int a[100010];
    int n;
    void  find(int x)//二分查找
    {
        
    	int low, high, m;
    	low = 0;
    	high = n - 1;
    	while (low <= high)
    	{
        
    		m = (low + high) / 2;
    		if (x < a[m])
    		{
        
    			high = m - 1;
    		}
    		else if (x > a[m])
    		{
        
    			low = m + 1;
    		}
    		else
    		{
        
    			printf("%d", m + 1);
    			return ;
    		}
    	}
    	printf("No Found!");
    	return ;
    }
    int main()
    {
        
    	int t,i,x;
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    	{
        
    		scanf("%d", &a[i]);
    	}
    	scanf("%d", &t);
    	for (i = 0; i < t; i++)
    	{
        
    		scanf("%d", &x);
    		find(x);
    		if (i != t - 1)
    		{
        
    			printf("\n");
    		}
    	}
    }

*刚看到题的时候，第一想法就是用一个大数组从头到尾遍历，对于测试的数据来说，答案是秒出的，但提交的时候提示“测试其他数据时超时”，这时想到了，如果想要找的数据在数组的最后，且数组空间为100000，那么时间就会太长，所以便采用了二分查找，二分查找的函数也不难理解。*

*C语言变量声明问题——变量定义一定要放在所有执行语句/语句块的最前面吗?对于这个问题我也上网查了一下，解答是这样的：.源文件保存为.c格式的话变量只能定义在最前，若保存为.cpp格式的话，变量定义较为灵活，不用在最前。在C语言里，变量只能在函数的开头处声明和定义。在函数里要用到的变量必须要在开头处声明定义。声明定义的前面不能有任何其他非声明定义的语句。**全局变量在函数体的外部声明定义。***