c - 如何在二进制搜索算法中找到倍数

Question

我想在二进制搜索中找到很多值问题是二进制搜索只找到第一个并返回它。我能找到我想要的数量吗？例如，假设我有这样的输入:

00001 1521065760 38 42' 50" -9 8' 22"
00001 1521066360 38 42' 4" -9 45' 24"
00001 1521066960 38 41' 18" -9 22' 26"
00001 1521067560 38 40' 32" -8 59' 28"
00001 1521068160 38 39' 46" -8 36' 30"
00001 1521068760 38 39' 2" -8 13' 32"
00001 1521069360 38 34' 0" -7 54' 0"
00001 1521069960 38 34' 0" -7 54' 0"
00002 1521065760 38 10' 33" -8 41' 35"
00002 1521066360 38 16' 14" -8 35' 36"
00002 1521066960 38 21' 55" -8 30' 20"
00002 1521067560 38 27' 36" -8 24' 44"
00002 1521068160 38 33' 17" -8 19' 8"
00002 1521068760 38 39' 2" -8 13' 32"
00002 1521069360 38 37' 16" -8 4' 50"
00002 1521069960 38 34' 0" -7 54' 0"

我想使用二进制搜索查找其中 'codigos'(id) differents 具有相同输入的位置，因此它将返回此值(00001 和 00002):

   1521068760 38 39' 2" -8 13' 32"
   1521069960 38 34' 0" -7 54' 0"

这是我的代码:

#include <stdio.h>
#include <stdlib.h>
struct suspeito{
   int codigo;
   int instante;
   int graulatitude;
   int minutolatitude;
   int segundolatitude;
   int graulongitude;
   int minutolongitude;
   int segundolongitude;
   };

  int PesquisaBinaria(int n, struct suspeito informacao[], int i, int j)
   {
     if (i > j)
        return -1;                  // o intervalo i..j é vazio

    int m = (i + j) / 2;          // ponto médio do intervalo

    if (n < informacao[m].codigo)
        // restringe a pesquisa ao intervalo i..m - 1
         return PesquisaBinaria(n, informacao, i, m - 1);

    if (n > informacao[m].codigo)
          // restringe a pesquisa ao intervalo m + 1..j
         return PesquisaBinaria(n, informacao, m + 1, j);

      // n == v[m]
    return m;
          } 
    int compare(const void *p1, const void *p2)
    {
     const struct suspeito *elem1 = (struct suspeito *)p1;
     const struct suspeito *elem2 = (struct suspeito *)p2;
     if (elem1->codigo < elem2->codigo)
         return -1;
     else if (elem1->codigo > elem2->codigo)
         return 1;
     else
         return 0;
       }
   int main()
      {


      struct suspeito informacao[10000];
        int codigo,instante,graulatitude,minutolatitude,segundolatitude,graulongitude,minutolongitude,segundolongitude;
int count,par1,par2;
while(1) {
    scanf(" %d",&codigo);
    if(codigo==0) {
        break;
    }
    scanf(" %d %d %d\' %d\" %d %d\' %d\"",&instante,&graulatitude,&minutolatitude,&segundolatitude,&graulongitude,&minutolongitude,&segundolongitude);
    informacao[count].codigo=codigo;
    informacao[count].instante=instante;
    informacao[count].graulatitude=graulatitude;
    informacao[count].minutolatitude=minutolatitude;
    informacao[count].segundolatitude=segundolatitude;
    informacao[count].graulongitude=graulongitude;
    informacao[count].minutolongitude=minutolongitude;
    informacao[count].segundolongitude=segundolongitude;
    count++;
}
qsort(informacao,count,sizeof(informacao[0]),compare);
printf("Codigo: %d\nInstante: %d\n",informacao[3].codigo,informacao[3].instante);

if(codigo==00000) {
    while(scanf(" %d %d",&par1,&par2)!=EOF) {
            int find1=PesquisaBinaria(par1,informacao,0,count);
            int find2=PesquisaBinaria(par2,informacao,0,count);
            if(find1==-1 && find2!=-1)
                printf("+ sem dados sobre o suspeito %d",par1);
            if(find1!=-1 && find2==-1)
                printf("+ sem dados sobre o suspeito %d",par2);
            if(find1!=-1 && find2!=-1) {
                printf("Index1:%d \nIndex2:%d\n",find1-1,find2-1);
                printf("Codigo1:%d\nInstante1:%d\nGrauLatitude1:%d\nMinutoLatitude1:%d\nSegundoLatitude1:%d\nGrauLongitude1:%d\nMinutoLongitude1:%d\nSegundoLongitude1:%d\n",informacao[find1-1].codigo,informacao[find1-1].instante,informacao[find1-1].graulatitude,informacao[find1-1].minutolatitude,informacao[find1-1].segundolatitude,informacao[find1-1].graulongitude,informacao[find1-1].minutolongitude,informacao[find1-1].segundolongitude);
                printf("Codigo2:%d\nInstante2:%d\nGrauLatitude2:%d\nMinutoLatitude2:%d\nSegundoLatitude2:%d\nGrauLongitude2:%d\nMinutoLongitude2:%d\nSegundoLongitude2:%d\n",informacao[find2-1].codigo,informacao[find2-1].instante,informacao[find2-1].graulatitude,informacao[find2-1].minutolatitude,informacao[find2-1].segundolatitude,informacao[find2-1].graulongitude,informacao[find2-1].minutolongitude,informacao[find2-1].segundolongitude);
                if(informacao[find1-1].instante==informacao[find2-1].instante && informacao[find1-1].graulatitude == informacao[find2-1].graulatitude && informacao[find1-1].minutolatitude==informacao[find2-1].minutolatitude && informacao[find1-1].segundolatitude == informacao[find2-1].segundolatitude && informacao[find1-1].graulongitude==informacao[find2-1].graulongitude && informacao[find1-1].minutolongitude==informacao[find2-1].minutolongitude && informacao[find1-1].segundolongitude==informacao[find2-1].segundolongitude)
                    printf("+ %05d e %05d podem ter-se encontrado em:\n",par1,par2);

            }
    }
    }



   }

Answer 1

您可以使用bsearch() 库函数。 但是，它返回一个任意对象而不是第一个匹配项。 然后您可以从 bsearch 结果向后迭代以找到第一个元素。原则上(使用 char * 而不是 void * 以获得更简单的代码)这可能看起来像:

    #include <stdlib.h>

    char * bsearch_first(char * key, char * arr, 
                         size_t cnt, size_t size, 
                         int(*cmp)(const void *, const void *)); 
    {
         char * result = bsearch(key,arr,cnt,size,cmp);

         if ( NULL != result ) {
             while ( arr < result && cmp(key, result - size) ) {
                 result -= size;
             }
         }
         return result;   
    }

另一种方法是从头开始实现 bsearch 变体。

然后遍历从 bsearch_first() 开始的所有元素，直到 cmp() != 0 或如果到达数组则结束:

    for ( item = bsearch_first(key,arr, ...);
          NULL != item 
            && item < (BYTE*)arr + sizeof arr
            && 0 == cmp(key,item);
          ++item )
    {
         do_stuff_with(item);
    }