Quickest way to search a uint16_t array for a uint16_t value?

Projects Programming
1

Hello,

I have an array of uint16_t values. What would be the quickest way to identify if the array contained a particular uint16_t value? I have been reading about memchr, but it only appears to compare 1 byte. My code is basically the following.

uint16_t myarray[10];
//put values in myarray
uint16_t somevalue =62000;

Now, I need to search "myarray" to determine if it contains "somevalue", need a function to return true or false. Any assistance would be appreciated.

Thanks,

-ren

2

Given the details you've provided the quickest way# is to sort the array and perform a binary search.

# Assuming "quickest way" means "the way that uses the least amount of CPU time".

3

CodingBadly,

Yes, least amount of cpu time is what I am looking for. Not sure how to sort and perform binary search, maybe I could just do a for loop and compare each value. Or I was thinking that I could use memchr, find 1st byte, then test for 2nd byte.

Thanks,

-ren

4

A straight linear search isn't that slow, for the number of items you can fit into memory. For example, worst-case:

const int MAX_ITEMS = 800;

int array [MAX_ITEMS];

void setup ()
  {
  array [MAX_ITEMS - 1] = 42;
  
  Serial.begin (115200);
  unsigned long start = micros ();
  boolean found = false;
  
  for (int i = 0; i < MAX_ITEMS; i++)
    if (array [i] == 42)
      {
      found = true;
      break;
      }
      
  unsigned long finish = micros ();
  
  Serial.print ("Time taken = ");
  Serial.print (finish - start);
  Serial.println (" uS");
  
  Serial.print ("Found = ");
  Serial.println (found);  
  }  // end of setup
  
void loop () {}

Output:

Time taken = 752 uS
Found = 1

That's under a millisecond. But if you want to better that, and the data is in sequence, you could use a binary search...

#include <iterator>
#include <algorithm>

const int MAX_ITEMS = 800;

int array [MAX_ITEMS];

void setup ()
  {
  unsigned long longest = 0;
  
  Serial.begin (115200);
  
  // each array element is its own position (this puts them in sequence)
  for (int i = 0; i < MAX_ITEMS; i++)
    array [i] = i;
  
  // try each one, see which is longest
  for (int i = 0; i < MAX_ITEMS; i++)
    {
    unsigned long start = micros ();
    bool found = std::binary_search(array, &array [MAX_ITEMS], i);
    unsigned long finish = micros ();
    
    if (!found)
      {
      Serial.print ("At position ");
      Serial.print (i);
      Serial.println (", not found, strange.");
      }
      
    longest = max (longest, finish - start);
    }
    
  Serial.print ("Time taken = ");
  Serial.print (longest);
  Serial.println (" uS");

  } // end of setup
  
void loop () {}

Output:

Time taken = 28 uS

That's somewhat faster. That algorithm is in the STL (Standard Template Library) although you could no doubt find your own by a Google search if you didn't want all of the STL.

5

Thanks Nick I will give it a try!