CODEWITHSUNDEEP
cstructbinary-search
Marie.L
Marie.L

Reputation: 11

How to use structs in binary search?

I'm trying to learn c (its my first language) and i have some problems with this task. (It is no homework!)

Task:

Implement the binary search algorithm on an array of structs of the following kind (sorry for my English).

    struct {
    unsigned int number;
    char* food;
    int price; 
} pk;

My code:

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


struct {
    unsigned int number;
    char* food;
    int price; 
} pk;


int binary search(int pk[], int l, int r, unsigned int number){
    int center;
    int start = l;
    int end = r;

    if (start == end){
        if (pk[start] == number){
            printf ("%d is in pk\n", number);   // do not know how to use the struct 
        }else{
            printf ("%d is not in pk\n", number);
            return -1;
        }
    }
    else {
        center = (start + end)/2;
        if (number <= pk[center]){
            return binary search(pk, start, center, number);
        }else{
            return binary search(pk, center+1, end, number);
        }
    }
}

My questions:
1) Could this code work?
2) How I can use this struct to fulfill the task, in my opinion I should to it complete different then now.

Upvotes: 0

Views: 2650

Answers (1)

chux
chux

Reputation: 153348

Enable all compiler warnings!

When if (start == end){ if (pk[start] == number){ is true, code returns nothing.

I'd expect return start; in this case.

Avoid start + end overflow

// center = (start + end)/2;
center = start + (end - start)/2;

Slightly different:
I'd recommend to return a pointer to the array on success and NULL on failure

// int binary search(pk a[], int l, int r, unsigned int number){
pk *binary search(pk a[], int l, int r, unsigned int number){
    int start = l;
    int end = r;

    if (start == end){
        if (a[start].number == number){
            printf ("%d is in a[] at index\n", number, start);
            return &a[start];
        }else{
            printf ("%d is not in a[]\n", number);
            return NULL;
        }
    }
    else {
        int center = start + (end - start)/2;
        if (number <= a[center].number){
            return binary search(a, start, center, number);
        }else{
            return binary search(a, center+1, end, number);
        }
    }
}

Advanced: Better code would use size_t for indexing and a const a[]

pk *binary search(const pk a[], size_t l, size_t r, unsigned int number){

Upvotes: 1

Related Questions