Функция Bsearch в C не работает должным образом - PullRequest
Новая
       23

Функция Bsearch в C не работает должным образом

0 голосов
/ 21 сентября 2018

В основном я создаю программу, которая будет выводить число, если оно найдено в заданном массиве, или выводить -1, если не найдено.(Sorted Array.) 

#include <stdio.h>
#include <stdlib.h>

int cmp(const void*a,const void *b){
    if(*(int*)a-*(int*)b>0) return 1;
    if(*(int*)a-*(int*)b<0) return -1;
    return 0;
}

int main() {
    int n; scanf("%d",&n);
    int a[n];

    for(int i =0;i<n;i++) 
        scanf("%d",a+i);

    for(int i =0;i<n;i++){
        int *item;
        item = (int*)bsearch(&i,a,n,sizeof(int),cmp);
        if(item!=NULL) printf("%d ",i);
        else printf("-1 "); 
    }

    return 0;
}

ВХОД: 10

-1 -1 6 1 9 3 2 -1 4 -1

ВЫХОД: -1 1 2 3 4 -1 6 -1 -1 9

Мой ВЫХОД: -1 -1 -1 3 4 -1 -1 -1 -1 -1

1 Ответ

0 голосов
/ 21 сентября 2018

https://www.tutorialspoint.com/c_standard_library/c_function_bsearch.htm

Функция библиотеки C void * bsearch (const void * key, const void * base, size_t nitems, size_t size, int (* сравнение) (const void *, constvoid *)) функция ищет в массиве объектов nitems, начальный член которого указан base, для члена, соответствующего объекту, на который указывает key.Размер каждого члена массива определяется размером.

Содержимое массива должно быть в порядке сортировки по возрастанию в соответствии с функцией сравнения, на которую ссылается сравнение.

Смысл бинарного поиска в том, что если массив имеет размер size, вы начинаете с позиции size/2.Если этот элемент меньше того, что вы ищете, перейдите к size/2 + size/4, а в противном случае перейдите к size/2 - size/4.Если этот подход должен работать, массив должен быть отсортирован.

Подробнее о бинарном поиске здесь: https://en.wikipedia.org/wiki/Binary_search_algorithm

И, как уже упоминалось в комментариях, scanf("%d",a+i) является правильным, но scanf("%d",&a[i]) предпочтительнее.

...