Pages: [1] 2   Go Down
Author Topic: Finding a number in a large array  (Read 1235 times)
0 Members and 1 Guest are viewing this topic.
Vancouver, Canada
Offline Offline
Full Member
***
Karma: 0
Posts: 118
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Offline Offline
Edison Member
*
Karma: 18
Posts: 1170
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hash table would be most efficient, otherwise Binary Search.
Logged

Finland
Offline Offline
Jr. Member
**
Karma: 1
Posts: 89
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Norfolk UK
Offline Offline
Edison Member
*
Karma: 52
Posts: 2214
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Handle every stressful situation like a dog. If you can't eat it or hump it. Piss on it and walk away.

Vancouver, Canada
Offline Offline
Full Member
***
Karma: 0
Posts: 118
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 11
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Logged

Global Moderator
UK
Offline Offline
Brattain Member
*****
Karma: 238
Posts: 24361
I don't think you connected the grounds, Dave.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

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

Vancouver, Canada
Offline Offline
Full Member
***
Karma: 0
Posts: 118
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Could you elaborate on this a little more...

Thanks
Logged

Global Moderator
UK
Offline Offline
Brattain Member
*****
Karma: 238
Posts: 24361
I don't think you connected the grounds, Dave.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
Could you elaborate on this a little more...
Certainly
Logged

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

Sydney, Australia
Offline Offline
Edison Member
*
Karma: 27
Posts: 1184
Big things come in large packages
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Arduino libraries http://arduinocode.codeplex.com
Parola hardware & library http://parola.codeplex.com

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Binary search is extremely efficient. I think it operates in log(n) where n is the number of entries.
Logged

Sweden
Offline Offline
Sr. Member
****
Karma: 6
Posts: 375
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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!
« Last Edit: July 30, 2013, 03:56:49 am by kowalski » Logged

Offline Offline
Edison Member
*
Karma: 18
Posts: 1170
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Global Moderator
UK
Offline Offline
Brattain Member
*****
Karma: 238
Posts: 24361
I don't think you connected the grounds, Dave.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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" ?
Logged

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

Norfolk UK
Offline Offline
Edison Member
*
Karma: 52
Posts: 2214
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Handle every stressful situation like a dog. If you can't eat it or hump it. Piss on it and walk away.

Pages: [1] 2   Go Up
Jump to: