Go Down

Topic: Finding a number in a large array (Read 1 time) previous topic - next topic

FardinB

Hi,

I want to find the index of 2 values A and B in a large array, from an input X, with the following conditions:
- the array will have values in an increasing order, and the values are all ints.
- the spacing of the values in the array is unknown
- X will be an input in the range of coverage of the array.
- A will be the closest number to X such that A < X
- B will be the closest number to X such that B > X
- if X is exactly equal to a number in the array, the index of that number will be returned.

I sort of know how to code this in arduino, but I was wondering what is the most efficient way and less clock cycles as possible way to do this...

Thanks

KeithRB

Hash table would be most efficient, otherwise Binary Search.

PetriH

How large is the array? It can't be very large if it fits into ATmega328P's SRAM... :)

Riva

If I understand you correctly (the array is in numeric size order) then...
subdivide the array (take the midpoint of the array) and check if it value is higher or lower than your target.
if the array value is lower subdivide the upper half again
if the array value is higher subdivide the lower half again
and so on until you get a match or the array will divide no more.
There are variations on this
http://forum.arduino.cc/index.php?action=unread;boards=5,67,10,11,66,12,15,17,21,22,23,24,25,29;ALL

FardinB

Thanks for the reply

I have the arduino mega 2560, and i will be storing the arrays in program memory...

Iterative method was what I was thinking as well. I just though there might be a faster way to do it...

Thanks

tock

hi
may be...
1. take first byte of desired int;
2. threat array of ints as array of bytes (see c union keyword)
3. iterate trought array of bytes
4. if match , compare second byte  etc..


AWOL

Quote
Iterative method was what I was thinking as well. I just though there might be a faster way to do it..

If it is fixed in ROM, you may as well sort it first before compilation, then use the binary search.
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

FardinB

Could you elaborate on this a little more...

Thanks

AWOL

Quote
Could you elaborate on this a little more...
Certainly
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

marco_c

All good advice so far but the quick- and binary- searches are designed to return the exact match for what you are looking for.

As I understand you want to find the next lowest and the next highest to the value you are looking for, so you will need to modify the algorithms presented.
Arduino libraries http://arduinocode.codeplex.com<br />Parola for Arduino http://parola.codeplex.com

Nick Gammon

Binary search is extremely efficient. I think it operates in log(n) where n is the number of entries.
http://www.gammon.com.au/electronics

kowalski

#11
Jul 30, 2013, 10:54 am Last Edit: Jul 30, 2013, 10:56 am by kowalski Reason: 1
And this is such a common problem that there is already a function in stdlib.h even for AVR.

See http://www.nongnu.org/avr-libc/user-manual/group__avr__stdlib.html#ga885c1ccefb716ff16ab73a57003140be
http://www.cplusplus.com/reference/cstdlib/bsearch/

And then just google bsearch for more example code.

BW: What is the original problem? My guess is that this is part of a larger problem and you have already done a design choice. As mentioned above a hashtab might be a better solution but it depends...

Cheers!

KeithRB

BTW, if you really want to learn about tis stuff, I recommend Sedgewick "Algorithms in C". You learn more than you thought possible about linked lists, searches, sorts and big Os.

AWOL

Quote
And this is such a common problem that there is already a function in stdlib.h even for AVR.

Is there a "bsearch_P" ?
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

Riva


Quote
And this is such a common problem that there is already a function in stdlib.h even for AVR.

Is there a "bsearch_P" ?

The problem with the AVR bsearch is it will only return a match but the OP wants to return a match or closest value(s) so they will need to code a similar version but one that suits there needs.
http://forum.arduino.cc/index.php?action=unread;boards=5,67,10,11,66,12,15,17,21,22,23,24,25,29;ALL

Go Up