Searching the Closest value

General
1

I need a simple way to know which value is closed in an array.

Lets say an array has the following values: 6,5,12,2,4,16,19,15.
Now, how can I now which array value is closes to for example 11. In this case that would be the array value 12 (3th in the array).

Any fast way to find this? Keep in mind the array could have 10.000’s of numbers. So using loops is not very fast I guess.

2

And you need the index or the value itself?

3

The value will do fine.
I got this working code, but it is very slow when you have +10.000 values in the array.

Dim a() As integer = Array(2, 42, 82, 122, 162, 202, 242, 282, 322, 362) MsgBox closest (111,a)

Public Function closest(numb as integer, a() as integer) as string dim curr as integer curr = a(0) for x as integer = 0 to a.Ubound if abs(numb-a(x)) < abs(numb-curr) then curr = a(x) end next x return str(curr) End Function

I tried to first sort the array, but that didn’t speedup things.
I need this to be calculated in ‘realtime’ (read: as fast as possible). Maybe Regex can help here?

4

What about a custom sort using the delegate method? Store your target in a property (or somewhere the sorter can find it), then return values based on how close they are to the target. The first value of the sorted array will be the answer.

5

I’m not sure that will be faster, of course, but it’s worth a shot. However, keep in mind that it will change the order of your array.

6

The way to speed this up:

  • sort the array
  • get the value at the half-point of the array
  • if it is larger than numb then the closest value must be in the bottom half of the array, so get the half-point value of the bottom half and compare it with numb. If it is smaller then it must be in the top half.
    Etc etc

So basically you trim the search space at each iteration down by a factor of two: 10,000 -> 5,000 -> 2,500 -> 1,250 -> 625 -> 312 -> 156 -> 78 -> 39 -> 20 -> 10 -> 5 -> 3 so after 12 iterations you are left with 3 values to compare.

I leave it to you to figure out the minutae. Just consider what is the closest value to 4? Both 2 and 6?

7

https://en.wikipedia.org/wiki/Binary_search_algorithm

8

Wait a second, I just tested this, and it takes about 5 ms to search 100,000 values in a compiled app.

Public Function Closest(arr() As Integer, target As Integer) as Integer
  dim found as integer = arr( 0 )
  dim diff as integer = abs( target - found )
  
  for i as integer = 1 to arr.Ubound
    dim test as integer = arr( i )
    if test = target then
      found = test
      exit
    end if
    
    dim thisDiff as integer = abs( test - target )
    
    if thisDiff < diff then
      diff = thisDiff
      found = test
    end if
  next
  
  return found
  
End Function
9

And probably even faster if you get the dims and Ubound out of the loop :slight_smile:

10

While it might make some difference on a micro scale, it won’t be as great as you might think. I once tested the difference between storing Ubound before the loop and using it directly, and it came down to microseconds over millions of iterations, so I decided it wasn’t worth the inconvenience. In this case, if either change made a difference, it wasn’t enough to measure.

Public Function Closest(arr() As Integer, target As Integer) as Integer
  dim found as integer = arr( 0 )
  dim diff as integer = abs( target - found )
  
  dim ub as integer = arr.Ubound
  dim test as integer
  dim thisDiff as integer
  
  for i as integer = 1 to ub
    test = arr( i )
    if test = target then
      found = test
      exit
    end if
    
    thisDiff = abs( test - target )
    
    if thisDiff < diff then
      diff = thisDiff
      found = test
    end if
  next
  
  return found
End Function
11

Thanks, Kem, that’s really good to know. I’ve been overly paranoid about this stuff, apparently, but never bothered to do benchmarks.

12

I talked to one fo the engineers about this many years ago at XDC and, if I remember correctly, it’s a property lookup rather than having to recalculate anything. Premature optimization is a programmers disease that afflicts many until they realize it doesn’t matter much and it’s easier to be lazy until you really need to look for the little speed enhancements. Usually it’s the UI that’s the slowest part, or any read/write to disk.

13

Just saw a bug. If the first element is a match, it should just return it.

14

Thank you for all the suggestions.

In the many tests I did, using Markus approach is the fastest. Sorting, start checking the middle value and then proceed accordingly.

15

I’m glad it worked for you, but I don’t understand it. Here, just the sort takes 7ms while the search takes 5. (On 100k items.)

16

On 1M items, the sort alone takes 67ms while the search takes around 40. Is the array already sorted?

18

Btw if it is a one-time operation then Kem’s brute force method should be fastest.

If it is a repeat operation then sorting the array and reusing the sorted array is much faster.

19

Personally, I love the binary search algorithm. The first time I heard about it was an “oh, wow!” moment for me.