游客 注册 | 登录
中文 | En

1368 - 算法9-2：有序表的折半查找

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB
用有序表表示静态查找表时，通常检索函数可以用折半查找来实现。
折半查找的查找过程是：首先确定待查记录所在的范围，然后逐步缩小范围直到找到或者确定找不到相应的记录为止。而每次需要缩小的范围均为上一次的一半，这样的查找过程可以被称为折半查找。
其查找过程可以描述如下： 

<span style="font-family:宋体;">在本题中，读入一串有序的整数，另外给定多次查询，判断每一次查询是否找到了相应的整数，如果找到则输出整数相应的位置。</span>


<span></span>

题目输入

输入的第一行包含2个正整数n和k，分别表示共有n个整数和k次查询。其中n不超过1000，k同样不超过1000。
第二行包含n个用空格隔开的正整数，表示n个有序的整数。输入保证这n个整数是从小到大递增的。
第三行包含k个用空格隔开的正整数，表示k次查询的目标。

题目输出

只有1行，包含k个整数，分别表示每一次的查询结果。如果在查询中找到了对应的整数，则输出其相应的位置，否则输出-1。
请在每个整数后输出一个空格，并请注意行尾输出换行。

输入/输出样例

输入格式

8 3
1 3 5 7 8 9 10 15
9 2 5

输出格式

5 -1 2

C语言解答

#include <stdio.h>
const int MAXN = 1000;

int main() {
        int a[MAXN];
        int n, k, query, l, r, mid;
        scanf("%d%d", &n, &k);
        for (int i = 0;i < n;i++) {
                scanf("%d", &a[i]);
        }
        for (int i = 0;i < k;i++) {
                scanf("%d", &query);
                l = 0;
                r = n;
                while (l < r) {
                        mid = (l + r) / 2;
                        if (a[mid] < query)
                                l = mid + 1;
                        else
                                r = mid;
                }
                if (a[l] == query)
                        printf("%d ", l);
                else
                        printf("-1 ");
        }
        puts("");
        return 0;
}

C++解答

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
int val[MAXN];
int main() {
	int n, k, query, l, r, mid;
	scanf("%d%d", &n, &k);
	for (int i = 0;i < n;i++) {
		scanf("%d", &val[i]);
	}
	for (int i = 0;i < k;i++) {
		scanf("%d", &query);
		l = 0;
		r = n;
		while (l < r) {
			mid = (l + r) / 2;
			if (val[mid] < query)
				l = mid + 1;
			else
				r = mid;
		}
		if (val[l] == query)
			printf("%d ", l);
		else
			printf("-1 ");
	}
	puts("");
	return 0;
}

Java解答



import java.util.Scanner;

public class Main{
  public static void main(String[] args) {
	  Scanner s = new Scanner(System.in) ;
	  
	  int n = s.nextInt() ;
	  int k = s.nextInt() ;
	  
	  if(n<=1000&&k<=1000){
		  int a[] = new int[n];
		  int b[] = new int[k];
		  for (int i = 0; i < a.length; i++) {
			  a[i] = s.nextInt() ;
		  }
		  for (int i = 0; i < b.length; i++) {
			  b[i] = s.nextInt() ;
		  }
		  
		  for (int i = 0; i < b.length; i++) {
			 for (int j = 0; j < a.length; j++) {
				if(b[i]==a[j]){
					System.out.print(j+" ") ;
					break ;
				}
				if(j==a.length-1){
					System.out.print(-1+ " ") ;
				}
			}
		  }
		  System.out.println() ;
	  }
  }
}
请先登陆