Breadth

Search for data in lists efficiently with optimal, unique needle-haystack searching algorithms.

Library

Eightomic Search A

The fastest sorted-list search algorithm versus Binary Search and Exponential Search.

unsigned char eightomic_search_a(unsigned long low,
                                 unsigned long high,
                                 const unsigned long *haystack,
                                 const unsigned long needle,
                                 unsigned long *position) {
  unsigned long gap;

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

  if (
    haystack[high] > needle &&
    haystack[low] < needle
  ) {
    high--;
    gap = high - low;

    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 (haystack[high] == needle) {
      *position = high;
      return 1;
    }

    return 0;
  }

  if (haystack[low] > needle) {
    high--;
    gap = high - low;

    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 (haystack[high] == needle) {
      *position = high;
      return 1;
    }

    return 0;
  }

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

  return 0;
}

eightomic_search_a() is the searching function for a list of elements already sorted in either ascending or descending order that accepts the following 5 arguments in left-to-right order.

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

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

3: haystack is the const unsigned long 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 unsigned long 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 unsigned long 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.

It's the fastest Binary Search optimization that works without knowing the sort order of the haystack elements.

It modifies the high bound instead of initializing with a median pivot value.

Subtraction is always the first operation on the high bound, so it decreases repeatedly in the same direction without either wasting CPU cycles on unnecessary conditional statements or exceeding the low bounds that are already verified to contain needle. This drastically decreases the number of gap calculations and comparisons in the average instance.

Furthermore, the positioning of conditional statements with gap calculations offset by + 1 prevents unnecessary array accesses and equality operations after each modification of the high bound. This drastically increases speed on average, especially for large arrays.

This process repeats in each iteration with alternating directions whenever the high bound almost exceeds the position of the needle element.

Compared to Binary Search, it's close to a lossless optimization with faster speed on average.

A specific best instance against Binary Search is demonstrated with the following code example.

#include <stdio.h>
#include "eightomic_search_a.h"

int main(void) {
  unsigned long input[111111];
  unsigned long position;
  unsigned long verification = 0;
  unsigned long i = 0;
  unsigned long j = 0;
  unsigned long k;

  while (i < 111111) {
    input[i] = i;
    i++;
  }

  while (j < 200) {
    i = 111111 - j;
    k = 11111 - j;

    while (k > 1000) {
      i--;

      if (eightomic_search_a(0, k, input, input[i], &position) != 0) {
        verification++;
      }

      k--;
    }

    j++;
  }

  printf("The verification is %lu.\n", verification);
  return 0;
}

Compared to Interpolation Search, it doesn't rely on evenly-distributed haystack values for heuristic calculations and it's substantially-faster than the worst case.

Compared to other sorted-list search algorithms for sorted arrays, it's faster across a wide range of data types and data, both randomized and uniform.

It's optimized for instances where low is greater than 0 and where needle is either found or not found in haystack.

#include <stdio.h>
#include "eightomic_search_a.h"

int main(void) {
  unsigned long input[111111];
  unsigned long position;
  unsigned long verification = 0;
  unsigned long i = 0;
  unsigned long j;
  unsigned long k;
  unsigned long low;
  unsigned long high;

  while (i < 111111) {
    input[i] = i | 3;
    i++;
  }

  while (i > 110000) {
    j = 0;

    while (j < 200) {
      k = 11110 - j;
      low = 0;
      high = 111101 - j;

      while (k > 10000) {
        k--;

        if (eightomic_search_a(low, high, input, input[k], &position) != 0) {
          verification++;
        }

        low++;
        high--;
      }

      j++;
    }

    i--;
  }

  printf("The verification is %lu.\n", verification);
  return 0;
}

Furthermore, the average speed is faster with randomized distribution using the aforementioned code with sorted numbers generated from various seeded PRNG states.

Different degrees of distribution are tested with bitwise OR operands 3, 7, 15 and so on.

The following code example demonstrates the aforementioned worst instance with Interpolation Search. It searches for 1 in an array with all values defined as 2 except for the first value defined as 0 and the second value defined as 1.

#include <stdio.h>
#include "interpolation_search.h"

int main(void) {
  unsigned long input[111111];
  unsigned long position;
  unsigned long verification = 0;
  unsigned long i = 0;
  unsigned long j = 0;
  unsigned long k;

  while (i < 111111) {
    input[i] = 2;
    i++;
  }

  input[0] = 0;
  input[1] = 1;
  input[2] = 2;

  while (j < 200) {
    i = 111100 - j;
    k = 111101 - j;

    while (i > 10000) {
      i--;

      if (interpolation_search_ascending(0, k, input, 1, &position) != 0) {
        verification++;
      }

      k--;
    }

    j++;
  }

  printf("The verification is %lu.\n", verification);
  return 0;
}

The aforementioned instance with Eightomic Search A is faster than the same instance with Binary Search.

Eightomic Search B

The fastest sorted-list search algorithm versus Interpolation Search.

It's not ready yet.

Eightomic Search C

The fastest search algorithm on average versus Sequential Search.

It's not ready yet.

License

Eightomic License

© Eightomic <https://eightomic.com>

Permission to both copy this software and use copies of this software is
granted only when the following 2 conditions are satisfied.

1. These software license conditions in entirety, both unmodified and without
   obfuscation, must be included wherever an instance of either a copy of this
   software or a derivation from a copy of this software is implemented.

2. Liability for damages incurred in conjunction with this software must not
   be assumed by Eightomic.