Go Down

### Topic: Quickest way to search a uint16_t array for a uint16_t value? (Read 2374 times)previous topic - next topic

#### renasis

##### Mar 24, 2012, 11:47 pm
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

#1
##### Mar 24, 2012, 11:51 pm

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".

#### renasis

#2
##### Mar 24, 2012, 11:59 pm

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

#### nickgammon

#3
##### Mar 25, 2012, 01:28 am
A straight linear search isn't that slow, for the number of items you can fit into memory. For example, worst-case:

Code: [Select]
`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:

Code: [Select]
`Time taken = 752 uSFound = 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...

Code: [Select]
`#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:

Code: [Select]
`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.
Please post technical questions on the forum, not by personal message. Thanks!