4D introduced binary searches on arrays back in V14 R4, so everyone with V15 and up has it. Who knew?
http://doc.4d.com/4Dv15/4D/15.3/Find-in-sorted-array.301-3152640.en.html What I can't find is a companion function for calculating the insert position of a new element. Having such a routine helps make Find in sorted array more useful. If you have to sort an array to search on it quickly, the sort may cost more than you save on the find. Instead, control insertion into the array so that it's always in sorted order without ever having to call SORT ARRAY. That doesn't make sense in every situation but, when it does, it's a great helper. As far as I can see, 4D doesn't have the function we need so I figured I'd write one. I did better than that and stole some old code from Dave Terry and updated it. (Posted below.) For those that don't already know about binary searches, they take advantage of the existing sort order to find elements more quickly (in general.) Instead of starting at the first element and scanning through to the end, you start in the middle and then go up/down depending on where your value hits. You progressively narrow the range of searches until you either hit a match or find where the element would go. Just like looking up a word in a dictionary or a name in a phone book. It's a core algorithm that many of you already know. For those that don't and for those that are rusty (cough-cough...not me, no never...), here are a few links: A very popluar and readable discussion that, unfortunately, uses a recursive implementation (Dave's code shows how unnecessary recursion is in this case. $50 fine for the first person to use "elegance" in combination with "recursion" in a sentence.) https://jeffreystedfast.blogspot.com.au/2007/02/binary-insertion-sort.html There are several related topics on the Wikipedia, but this article looks pretty on the mark: https://en.wikipedia.org/wiki/Binary_search_algorithm I started to adapt the version from https://jeffreystedfast.blogspot.com.au/2007/02/binary-insertion-sort.html ...but hated the pointless recursion. I remembered that Dave Terry had written this up years ago and dug up a copy of the note. Unfortunately, these older notes are not listed in the KB, even when they still apply. Hey! 4D guys! There's lots of great stuff in the old notes that you could strip mine for new material. Find just about anything by Dave Terry or Nicolas Barcet, as a starting point. Anyway, here's Dave's code, updated and slightly tweaked: If (False) // Array_BinaryFindPosition // Adapted from "Binary Searches:, ACI US Technical note #28, May 1991 by Dave Terry. // Notes and changes: // * Updated to current version of 4D language. // * Various tweaks to variable names. // * Poured on a bit of extra syntactic sugar to make sure that 4D sorts through // the pointers correctly. // * Change in behavior: A value past the end of the array returns Size of array+1. // Dave's code returned Size of array instead. (Deliberately.) For insert operations, // it is more useful to get back where the element should go. As a consequence, you need // to test if the index is past the end of the array or not. // * Change of behavior: Dave expected string values, I'm using pointers to array and value. End if C_LONGINT($0;$result) C_POINTER($1;$array_pointer) C_POINTER($2;$value_pointer) $array_pointer:=$1 $value_pointer:=$2 C_LONGINT($high) C_LONGINT($low) C_LONGINT($current) C_LONGINT($size_of_array) $size_of_array:=Size of array($array_pointer->) Case of : (($value_pointer->)<=($array_pointer->{1})) $result:=1 // Less than or equal to item 1, use item 1. : (($value_pointer->)=($array_pointer->{$size_of_array})) $result:=$size_of_array // Equal to the last item, return it. : (($value_pointer->)>($array_pointer->{$size_of_array})) $result:=$size_of_array+1 // It's greater than the last element, specify new position. ** This element does not exist yet. ** Else $low:=1 $high:=Size of array($array_pointer->) Repeat $current:=$high+$low\2 If ($value_pointer->>$array_pointer->{$current}) $low:=$current Else $high:=$current End if Until ($low>=($high-1)) $result:=$high End case $0:=$result I have only done limited testing on this but will be using the code next week. If anyone finds problems or can suggest improvements, let me know. The only test code I've run so far is for find, not insert and only with longints. Here it is: // Quick-and-dirty checking code for binary position function. // Not final test code, insert not proofed. // Build a sorted array ARRAY LONGINT($array_longint;0) APPEND TO ARRAY($array_longint;1) APPEND TO ARRAY($array_longint;2) APPEND TO ARRAY($array_longint;3) APPEND TO ARRAY($array_longint;4) APPEND TO ARRAY($array_longint;5) APPEND TO ARRAY($array_longint;6) APPEND TO ARRAY($array_longint;6) APPEND TO ARRAY($array_longint;8) APPEND TO ARRAY($array_longint;9) APPEND TO ARRAY($array_longint;10) // Prepare a dump report C_TEXT($dump) $dump:="" $dump:=$dump+"Value"+Char(Tab) $dump:=$dump+"Position"+Char(Carriage return) // Loop through the array testing where each item should go. // Since we're checking the array contents themselves, each item // should return it's actual position. C_LONGINT($size_of_array) C_LONGINT($index) $size_of_array:=Size of array($array_longint) C_LONGINT($index) For ($index;1;$size_of_array) C_LONGINT($result) $result:=Array_BinaryFindPosition (->$array_longint;->$index) $dump:=$dump+String($index)+Char(Tab)+String($result)+Char(Carriage return) End for // Try a value that is lower than any in the array. It should return 1. C_LONGINT($test_value) $test_value:=-1 $result:=Array_BinaryFindPosition (->$array_longint;->$test_value) $dump:=$dump+String($test_value)+Char(Tab)+String($result)+Char(Carriage return) // Try a value that is higher than any in the array. It should return Size of array +1 (10). $test_value:=13 $result:=Array_BinaryFindPosition (->$array_longint;->$test_value) $dump:=$dump+String($test_value)+Char(Tab)+String($result)+Char(Carriage return) // Grab the text and have a look at it. SET TEXT TO PASTEBOARD($dump) Here's what my output looks like: Value Position 1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 8 9 9 10 10 -1 1 13 11 ********************************************************************** 4D Internet Users Group (4D iNUG) FAQ: http://lists.4d.com/faqnug.html Archive: http://lists.4d.com/archives.html Options: http://lists.4d.com/mailman/options/4d_tech Unsub: mailto:[email protected] **********************************************************************
