Home

Bsearch

Replace bsearch() for faster Binary Search speed in security-compliant C/C++ systems.

Algorithm

Source

#include <stdint.h>

unsigned char eightomic_bsearch_ascending(uintptr_t low, uintptr_t high,
                                          const int *haystack,
                                          const int needle,
                                          uintptr_t *position) {
  uintptr_t gap;

  if (haystack[low] < needle) {
    if (haystack[high] < needle) {
      return 0;
    }

    if (haystack[high] == needle) {
      *position = high;
      return 1;
    }

    high--;
    gap = high - low;

    if (gap > 2) {
      while (haystack[high] > needle) {
        while (haystack[high] > needle) {
          high -= gap >> 1;
          gap = (gap >> 1) + 1;
        }

        while (haystack[high] < needle) {
          high += gap >> 1;
          gap = (gap >> 1) + 1;
        }

        if (gap < 3) {
          break;
        }
      }
    }

    while (haystack[high] > needle) {
      high--;
    }

    if (haystack[high] == needle) {
      *position = high;
      return 1;
    }

    return 0;
  }

  if (haystack[low] == needle) {
    *position = low;
    return 1;
  }

  return 0;
}

unsigned char eightomic_bsearch_descending(uintptr_t low, uintptr_t high,
                                           const int *haystack,
                                           const int needle,
                                           uintptr_t *position) {
  uintptr_t gap;

  if (haystack[low] > needle) {
    if (haystack[high] > needle) {
      return 0;
    }

    if (haystack[high] == needle) {
      *position = high;
      return 1;
    }

    high--;
    gap = high - low;

    if (gap > 2) {
      while (haystack[high] < needle) {
        while (haystack[high] < needle) {
          high -= gap >> 1;
          gap = (gap >> 1) + 1;
        }

        while (haystack[high] > needle) {
          high += gap >> 1;
          gap = (gap >> 1) + 1;
        }

        if (gap < 3) {
          break;
        }
      }
    }

    while (haystack[high] < needle) {
      high--;
    }

    if (haystack[high] == needle) {
      *position = high;
      return 1;
    }

    return 0;
  }

  if (haystack[low] == needle) {
    *position = low;
    return 1;
  }

  return 0;
}

License

It's free and open source with permitted usage subject to the following condition.

The function names eightomic_bsearch_ascending() and eightomic_bsearch_descending() must not change.

Reference

eightomic_bsearch_ascending() and eightomic_bsearch_descending() are the searching functions for a list of elements already sorted in either ascending or descending order that accept the following 5 arguments in left-to-right order.

1: low is the uintptr_t lowest index bound to search in haystack.

2: high is the uintptr_t highest index bound to search in haystack and must be greater than or equal to low.

3: haystack is the const int array of elements to search. The data type is interchangeable with any integral data type after modifying the relevant function parameter accordingly.

4: needle is the const int element to search for in haystack. The data type is interchangeable with any integral data type after modifying the relevant function parameter to match the haystack data type.

5: position is the uintptr_t pointer containing the index of the searched element.

The return value data type is unsigned char. When the return value is 1, position contains the index of the found needle.

When the return value is 0, a new index value isn't assigned to position.

Speed

Eightomic Bsearch is close to a lossless optimization with faster speed than Binary Search, Exponential Search and Fibonacci Search in all distributed instances that were tested by Eightomic.

It doesn’t rely on evenly-distributed haystack values for heuristic, input-based calculations and it's substantially-faster than the worst instances of Interpolation Search.

It's possibly the fastest sorted-list search algorithm compared to sorted-list search algorithms that don't require input-based calculations across a wide range of data types and data, both randomized and uniform.

Security

bsearch() doesn't guarantee the use of Binary Search and has neither space nor time complexity guarantees.

Eightomic Bsearch is an optimal alternative to every instance that implements bsearch() to perform a needle-in-a-haystack search operation on a sorted list of elements.

The following security explanation uses the context of ascending sort order.

if (haystack[low] < needle) ensures needle is larger than the low bound in haystack before proceeding. If not, it falls through to verify the low bound in haystack before exiting.

Otherwise, if (haystack[high] < needle) ensures needle is contained within haystack, then verifies the high bound in haystack.

In addition to the aforementioned conditional statements creating the fastest instance whenever needle isn’t found, they set up a safe range to iterate through without requiring additional comparisons for memory safety.

Then, high-- decreases the previously-verified high bound to prevent overflows in the core searching loop while maintaining the searchability of each element in haystack.

Instead of initializing with a median pivot value before determining a search direction, the high bound is halved, meaning the first Binary Search operation always uses subtraction repeatedly before proceeding in the opposite direction.

The aforementioned alternating control flow prevents excessive array accesses and equality operations after each modification of the high bound to increase speed without either exceeding bounds or skipping elements.

The aforementioned process repeats until either gap is 2 or the high bound is greater than or equal to needle.

Then, to avoid infinite loops, it processes a final one-way Binary Search operation as if gap is 1.

The final conditional statement if (haystack[high] == needle) verifies if the resulting high bound in haystack contains needle.