RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1200886
Accepted
A_Hatake
A_Hatake
Asked:2021-11-06 20:25:16 +0000 UTC2021-11-06 20:25:16 +0000 UTC 2021-11-06 20:25:16 +0000 UTC

二进制元素搜索

  • 772

需要对已排序数组中具有给定值的元素进行二进制搜索。第一行包含一个整数 𝑁 — 排序数组的大小 (1 <= 𝑁 <= 10^5)。接下来,写入数组𝐴𝑖(整数的𝑁,|𝐴𝑖| <= 10^9)的元素。然后写入一个整数 𝑄 — 需要处理的请求数 (1 <= 𝑄 <= 10^5)。剩下的 𝑄 行包含定义搜索查询的整数 𝑋𝑗。每个请求必须按如下方式处理。首先,您需要将前面查询的答案𝑅𝑗−1 添加到文件中写入的数字𝑋𝑗,得到𝑌𝑗 = 𝑋𝑗 + 𝑅𝑗−1。然后你需要在数组𝐴中找到一个等于𝑌𝑗的元素:它的索引将是这个查询的答案𝑅𝑗。如果有很多这样的元素,那么应该选择最大的索引作为答案𝑅𝑗。如果没有这样的元素,那么答案𝑅𝑗是-1。数组元素的索引从 0 到𝑁 − 1。第一个查询没有先前的答案,所以我们把 𝑌0 = 𝑋0。 告诉我如何改进程序:

#include <stdio.h>
#include <malloc.h>
#include <conio.h>

int binarysearch(int a, int mass[], int n);
void InsertionSort(int n, int mass[]);

int main()
{
    int N, a;
    printf("Input N: ");
    scanf_s("%d", &N);
    int* mass;
    mass = (int *)malloc(N * sizeof(int));
    printf("Input the array elements:\n");
    for (int i = 0; i < N; i++)
        scanf_s("%d", &mass[i]);
    InsertionSort(N, mass);
    printf("Sorted array:\n");
    for (int i = 0; i < N; i++)
        printf("%d ", mass[i]);
    printf("\n");
    printf("Input variable 'a' for search: ");
    scanf_s("%d", &a);
    int k;
    k = binarysearch(a, mass, N);
    if (k != -1)
    {
        printf("The index of the element is %d\n", k);
    }
    else
        printf("The element isn't found!\n");
    free(mass);
    _getch();
    return 0;
}

int binarysearch(int a, int mass[], int n)
{
    int low, high, middle;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        middle = (low + high) / 2;
        if (a < mass[middle])
            high = middle - 1;
        else if (a > mass[middle])
            low = middle + 1;
        else 
            return middle;
    }
    return -1;
}

 
void InsertionSort(int n, int mass[])
{
    int newElement, location;

    for (int i = 1; i < n; i++)
    {
        newElement = mass[i];
        location = i - 1;
        while (location >= 0 && mass[location] > newElement)
        {
            mass[location + 1] = mass[location];
            location = location - 1;
        }
        mass[location + 1] = newElement;
    }
}

UPD: 我能够搞砸一些事情,但测试系统说程序没有通过所有测试。怎么了???

#include<stdio.h>
int a[1000000];
int main()
{
int N,Q,c;
scanf("%d",&N);
if (N!=0){
int x,y=0,z=0;
for(int i=0;i<N;i++)
{
scanf("%d",&c);
a[c]=i;
}
scanf("%d",&Q);
for(int i=0;i<Q;i++)
{
scanf("%d",&x);
y+=x;
int j=0;
int flag=0;
z=a[y];
if (z!=0)
{
flag=1;
}
y=z;
if (flag==0)
y=-1;
printf("%d\n",y);
j++;
}
return(0);
}
}
c
  • 2 2 个回答
  • 10 Views

2 个回答

  • Voted
  1. MBo
    2021-11-07T00:24:16Z2021-11-07T00:24:16Z

    该条件似乎在谈论排序数组,因此您可能不需要对其进行排序。毕竟,如果输入数据没有排序,那么对于 10^5 的数组大小,InsertionSort 是一个不好的选择,您需要使用更快的排序 -qsort()在标准库中可用。

    此外,если таких элементов много, то в качестве ответа 𝑅𝑗 следует выбрать самый большой индекс.意味着使用返回最右边元素的二进制搜索修改 - wiki

    function binary_search_rightmost(A, n, T):
        L := 0
        R := n
        while L < R:
            m := floor((L + R) / 2)
            if A[m] > T:
                R := m
            else:
                L := m + 1
        return R - 1
    
    • 1
  2. Best Answer
    Harry
    2021-11-11T20:58:39Z2021-11-11T20:58:39Z

    坦率地说,我认为需要像查询优化这样的东西 - 好吧,根据之前的解决方案查看可能的范围,但一切都证明是多余的 - 重复通常的简单二进制搜索就足够了......

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    int a[100000];
    
    int* upper_bound(int* first, int* last, int value)
    {
        int * it;
        int count = last-first, step;
        while (count > 0)
        {
            it = first; 
            step = count / 2;
            it += step;
            if (!(value < *it))
            {
                first = ++it;
                count -= step + 1;
            } 
            else
                count = step;
        }
        return first;
    }
    
    int main()
    {
        int N, Q, R = 0, X;
        scanf("%d",&N);
        for(int i = 0; i < N; ++i) scanf("%d",a+i);
        scanf("%d",&Q);
        for(int i = 0; i < Q; ++i)
        {
            scanf("%d",&X);
            X += R;
            int * f = upper_bound(a,a+N,X);
            if (*(f-1) != X) R = -1; else R = f-1-a;
            printf("%d\n",R);
        }
    }
    
    • 1

相关问题

  • free 出于某种原因不会从内存中删除数组

  • 请帮助代码

  • 为什么 masm 对字符串或文本文字太长发誓,为什么在结构中设置 db 或 dw?

  • 如何将数字拆分为位并将其写入 C 中的数组?

  • 如何以给定的角度移动物体?

  • 解决“子集和问题”的时效算法

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    如何从列表中打印最大元素(str 类型)的长度?

    • 2 个回答
  • Marko Smith

    如何在 PyQT5 中清除 QFrame 的内容

    • 1 个回答
  • Marko Smith

    如何将具有特定字符的字符串拆分为两个不同的列表?

    • 2 个回答
  • Marko Smith

    导航栏活动元素

    • 1 个回答
  • Marko Smith

    是否可以将文本放入数组中?[关闭]

    • 1 个回答
  • Marko Smith

    如何一次用多个分隔符拆分字符串?

    • 1 个回答
  • Marko Smith

    如何通过 ClassPath 创建 InputStream?

    • 2 个回答
  • Marko Smith

    在一个查询中连接多个表

    • 1 个回答
  • Marko Smith

    对列表列表中的所有值求和

    • 3 个回答
  • Marko Smith

    如何对齐 string.Format 中的列?

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5