Go Down

### Topic: Finding a number in a large array (Read 3163 times)previous topic - next topic

#### FardinB

##### Jul 29, 2013, 06:34 pm
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

#1
##### Jul 29, 2013, 06:44 pm
Hash table would be most efficient, otherwise Binary Search.

#### PetriH

#2
##### Jul 29, 2013, 06:52 pm
How large is the array? It can't be very large if it fits into ATmega328P's SRAM...

#### Riva

#3
##### Jul 29, 2013, 06:58 pm
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
Don't PM me for help as I will ignore it.

#### FardinB

#4
##### Jul 29, 2013, 08:11 pm

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

#5
##### Jul 29, 2013, 09:53 pm
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

#6
##### Jul 29, 2013, 09:54 pm
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

#7
##### Jul 29, 2013, 10:43 pm
Could you elaborate on this a little more...

Thanks

#### AWOL

#8
##### Jul 29, 2013, 10:44 pm
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

#9
##### Jul 30, 2013, 10:18 am
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
Parola for Arduino http://parola.codeplex.com
Arduino++ blog https://arduinoplusplus.wordpress.com

#### Nick Gammon

#10
##### Jul 30, 2013, 10:49 am
Binary search is extremely efficient. I think it operates in log(n) where n is the number of entries.
Please post technical questions on the forum, not by personal message. Thanks!

http://www.gammon.com.au/electronics

#### kowalski

#11
##### Jul 30, 2013, 10:54 amLast 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

#12
##### Jul 30, 2013, 04:13 pm
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

#13
##### Jul 30, 2013, 04:20 pm
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

#14
##### Jul 30, 2013, 05:14 pm

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.
Don't PM me for help as I will ignore it.

Go Up

Please enter a valid email to subscribe