二分查找1

zcmu:

1099: 查找元素II

Time Limit: 1 Sec Memory Limit: 128 MB

[Submit][Status][Web Board]

Description

給定一個整數集合s,集合中有n個元素,我有m次詢問,對于每次詢問給定一個整數x,若 x存在于集合s中輸出x found at y,y為集合s按從小到大排序後第一次出現x的下标,否則輸出x not found.

Input

多組測試資料,每組第一行為兩個正整數n,m.(1<=n,m<=1000)代表集合中元素的個數和查詢次數,接下來n行每行有一個正整數代表集合裡的元素.(每個整數的大小小于等于100000),接下來 m行每行有一個正整數代表查詢的元素.

Output

詳見sample output

Sample Input

4 1

2

3

5

1

5

5 2

1

3

3

3

1

2

3

Sample Output

CASE# 1:

5 found at 4

CASE# 2:

2 not found

3 found at 3

HINT

Source

//好久前寫的，現在拿出來當總結

Ac_code~:

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1005],b[1005];
int search2(int aim,int a[],int l)//二分法查找
{
    int top=0,tail=l-1,z,f=-1;
    while(top<=tail)
    {
        z=(tail+top)/2;
        if(aim<a[z])
        {
            tail=z-1;
        }
        else if(aim>a[z])
        {
            top=z+1;
        }
        else
        {
            f=z;
            break;
        }
    }
    return f;
}
int main()
{
    int n,m,k=0;
    while(~scanf("%d%d",&n,&m))
    {
        k++;
        int i,j,w;
        for(i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        for(j=0; j<m; j++)
        {
            scanf("%d",&b[j]);
        }
        printf("CASE# %d:\n",k);
        for(i=0; i<m; i++)
        {
            w=search2(b[i],a,n);//查詢到傳回數組下标值，否知傳回的為-1
            if(w==-1) printf("%d not found\n",b[i]);
            else
            {
                for(j=w-1; j>=0; j--)
                {
                    if(a[w]!=a[j]) break;
                    else w=j;
                }
                printf("%d found at %d\n",b[i],w+1);
            }
        }
    }
    return 0;
}