2
\$\begingroup\$

This is an indirect follow-up to this post.

I've tried to assimilate all that was instructed and here's my attempt at binary search.

binary_search.h

#ifndef _BINARY_SEARCH_H
#define _BINARY_SEARCH_H

/*
 * Summary:
 *  Performs binary search on the given sorted array using the given
 * comparator function. Returns the index of the matching array
 * element (< count), and -1 if the element is not found.
 *
 *  Parameters are independent of type and hence this function
 * can be used for arrays of all data-types, provided that the size
 * (i.e. in terms of bytes) is properly specified.
 *
 * CAUTION: It will not work on unsorted arrays.
 *
 * Parameters:
 *  1. *x    - the address of the element to find in the array
 *  2. *base - the address of the sorted array from whence we start searching.
 *  3. count - the maximum number of elements we are willing to search against.
 *  4. size  - the size of each element of the array (in bytes)
 *  5. compare(void*, void*)
 *           - the function which is used for comparison. Zero is taken to be equality.
 */
void *binary_search(const void *x, const void *base, size_t count, size_t size,
                    int (*compare)(const void *, const void *));

#endif

binary_search.c

#include <stdlib.h>

void *binary_search(const void *x, const void *base, size_t count, size_t size,
                    int (*compare)(const void *, const void *))
{
    char *base_ptr = (char *) base;
    size_t lo = 0, hi = count - 1, mid;
    while (lo <= hi) {
        mid = lo + ((hi - lo) >> 1);
        int result = (*compare)(base_ptr + mid * size, x);
        if (result == 0) {
            return base_ptr + mid * size;
        } else if (result < 0) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return NULL;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "binary_search.h"

int compare(const void *a, const void *b)
{
    const double *p = a;
    const double *q = b;
    // The convention is to send the NaNs to the end, so
    // they are considered to be greater than others here.
    if (isnan(*p)) return +1;
    if (isnan(*q)) return -1;
    // An elegant way to convert the result to int:
    return (*p > *q) - (*p < *q);
}

int main(int argc, char const *argv[])
{
    double *a, *result;
    double x;
    size_t size, count, i;
    double aa = .1, bb = .1;
    size = sizeof(double);

    printf("Enter how many elements : ");
    scanf("%llu", &count);

    a = malloc(count * size);
    if (a == NULL) {
        printf("Error while trying to allocate memory.\n");
        return EXIT_FAILURE;
    }

    printf("Enter elements one-by-one:\n");
    for (i = 0; i < count; i++) {
        printf("%u : ", (i + 1));
        scanf("%lf", (a + i));
    }

    printf("Enter the element to look for : ");
    scanf("%lf", &x);
    result = binary_search(&x, a, count, size, compare);

    if (result) {
        printf("Element found. Index is %u\n", (result - a));
    } else {
        printf("Element not found.\n");
    }

    return EXIT_SUCCESS;
}

Same request. Suggestions and critique are welcome.


Update

In main.c, the line double aa = .1, bb = .1; is unnecessary. I forgot to remove it after debugging. You may disregard it.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Code does not handle an array size of 0 (count == 0). Simple to fix

//size_t lo = 0, hi = count - 1, mid;
//while (lo <= hi) {

size_t lo = 0, hi = count, mid;
while (lo < hi) {
  hi--;

Potential UB. Consider the below if mid == 0. IMO, better to use a variable hi_plus_1 instead of hi and adjust code accordingly to avoid size_t underflow.

        hi = mid - 1;  // hi could become SIZE_MAX

Avoid losing const-ness.

const void *base
// char *base_ptr = (char *) base;
const char *base_ptr = (const char *) base;

binary_search.c is missing the include of binary_search.h. This is important to maintain the consistency of the declaration and definition.

binary_search.h should include <stdlib.h> for size_t.

#include "binary_search.h"

void *binary_search(const void *x, const void *base, size_t count, size_t size,
    int (*compare)(const void *, const void *)) {
  const char *base_ptr = (const char *) base;
  size_t lo = 0, hi_plus1 = count;
  while (lo < hi) {
    size_t mid = lo + (hi_plus1 - lo)/2;
    int result = (*compare)(base_ptr + mid * size, x);
    if (result == 0) {
      return base_ptr + mid * size;
    } else if (result < 0) {
      lo = mid + 1;
    } else {
      hi_plus1 = mid;
    }
  }
  return NULL;
}

Test code

Problem specifier. Use "%zu" for size_t. The 2 below hint OP is not compiling with all warnings enabled. Double-check that all warnings are enabled for prompt automatic feedback.

 size_t count, i;
 // scanf("%llu", &count);
 scanf("%zu", &count);

 for (i = 0; i < count; i++) {
    // printf("%u : ", (i + 1));
    printf("%zu : ", (i + 1));

A size of 0 may cause for malloc() to return NULL and that is not an out-of-memory.

 a = malloc(count * size);
 // if (a == NULL) {
 if (a == NULL && count > 0) {
   printf("Error while trying to allocate memory.\n");

size = sizeof(double); lacks context. Why sizeof(double)? Certainly that is because that is the type a points to. Then code that directly:

// size = sizeof(double);
size = sizeof *a;

For testing, useful to print the value sought and the value found. Recommend %e for detail.

printf("Value sought %e\n", x);
printf("Value found  %e\n", x, *result);
// or for sufficient detail
printf("Value sought %.*e\n", DBL_DECIMAL_DIG - 1, x);
printf("Value found  %.*e\n", DBL_DECIMAL_DIG - 1, *result);

With compare(), note that 0.0 will match -0.0. If that is not desired, perhaps below. Simplifications may be possible.

int compare(const void *a, const void *b) {
    const double *p = a;
    const double *q = b;
    if (*a > *b) return 1;
    if (*a < *b) return -1;
    if (isnan(*p)) return +1;
    if (isnan(*q)) return -1;

    // values are equal and not NaNs
    if (!signbit(*a) == !signbit(*b)) return 0;
    if (signbit(*a)) return -1;
    return 1;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.