Skip to content

14262: 【原4262】Search

题目

题目描述

author: ljx 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4262

Search

给定一个长度为$n$的已经从小到大排序的数字各不相同的序列,一个范围$[start,end]$,和一个$key$,你需要查找区间$[start,end]$之间是否有$key$。 如果有,输出key所在位置;如果无,输出-1. 请注意,输入序列是0-base.

INPUT

第一行一个正整数$n$。 第二行$n$个正整数,表示整个序列,保证序列已经从小到大排序,且序列中的数字各不相同。 第三行三个正整数,$start,end,key$,含义对应题面。

OUTPUT

一行,表示key所在位置,如未找到,输出-1.

SAMPLE INPUT

5
1 2 3 4 5
0 3 2

SAMPLE OUTPUT

1

HINT

给定sample.cpp如下:

#include <iostream>
#include <cstdio>
using namespace std;

int a[1000005];

int WORK(int n, int start, int end, int key)
{
    int ret = -1;
    //TODO
    //只要满足start <= end 就执行以下事情,否则代表未找到key,退出循环
    //取mid为start和end的平均数且向下取整
    //比较数组a第mid个数x和key的大小:
    //如果x恰好和key相等,说明mid就是需要的答案,把位置存在ret内,退出循环
    //如果x比key小,说明key位于数组mid位置的右半部分,把最左端start移动到mid+1的位置,表明下一次只用在[mid+1,end]范围内查找
    //如果x比key大,操作类似

    return ret;
}

int main()
{
    int n, key, start, end;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    scanf("%d%d%d", &start, &end, &key);
    int ans = WORK(n, start, end, key);
    printf("%d\n", ans);
    return 0;
}

读入和各个变量的定义已经为你提供,你只需要完成//TODO部分的内容。算法描述请见程序中的注释。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!