Day5：查找

例5.1查找第k小数

时间限制：1s 空间限制：64M

题目描述

查找一个数组的第K小的数，注意同样大小算一样大。 如 2 1 3 4 5 2 第三小数为3。

输入描述:

输入有多组数据。
每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。

输出描述:

输出第k小的整数。

示例输入

6
2 1 3 5 2 2
3

示例输出

3

代码5.1.1 解法一：选择排序+数组去重

#include <stdio.h>

int main()
{
    int n, k;
    int A[1000];
    while(scanf("%d", &n) != EOF)
    {
        for( int i = 0; i < n; i++)
        {
            scanf("%d", &A[i]);
        }
        scanf("%d", &k);
        for(int i = 0; i < n - 1; i++) //n-1趟选择排序
        {
            int min = i;
            for(int j = i+1; j < n; j++)
            {
                if( A[j] < A[min] )
                    min = j;
            }
            if( min != i){
                int temp = A[min];
                A[min] = A[i];
                A[i] = temp;
            }
        }
        //数组去重
        int m = 0;
        for(int i = 0; i < n - 1; i++)
        {
            if(A[i] != A[i+1])
                A[m++] = A[i];
        }
        printf("%d", A[k-1]);
    }
}

例5.2找x

时间限制：1s 空间限制：64M

题目描述

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

输入描述:

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

输出描述:

对于每组输入,请输出结果。

示例输入

2
1 3
0

示例输出

-1

代码5.2.1

#include <stdio.h>

int main()
{
    int n, x;
    int A[200];
    int ans = -1;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &A[i]);
        }
        scanf("%d", &x);
        for(int i = 0; i < n; i++)
        {
            if(A[i] == x)
            {
                ans = i;
                break;
            }           
        }
        printf("%d", ans);
    }
    return 0;
}

代码5.2.2 若输入数据有序：二分查找

#include <stdio.h>

int main()
{
    int n, x;
    int A[200];
    int ans = -1;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &A[i]);
        }
        scanf("%d", &x);
        int low = 0;
        int high = n-1;
        while(low <= high)
        {  
            int mid = ( low + high ) / 2;
            if(A[mid] == x)
            {
                ans = mid;
                break;
            }
            else if(A[mid] < x)
                low = mid + 1;
            else
                high = mid - 1;
        }
        printf("%d", ans);
    }
    return 0;
}