Thanks to Vincent and mghilissen for the idea! This version returns the indices in the right order:
on MultiBinarySearch(theList, value, l, r)
script o
property lst : theList
property indices : {}
on mbsrch(l, r)
if (item l of my lst is value) then set end of my indices to l
set l to l + 1
set m to (l + r) div 2
if (m ≥ l) and ({value} is in items l thru m of my lst) then mbsrch(l, m)
set m to m + 1
if (r ≥ m) and ({value} is in items m thru r of my lst) then mbsrch(m, r)
end mbsrch
end script
o's mbsrch(l, r)
return o's indices
end MultiBinarySearch
set theList to {"a", "b", "c", "d", "e", "f", "a", "g", "h", "i", "j", "k", "a", "l", "m", "m", "o", "p", "a", "e"}
MultiBinarySearch(theList, "a", 1, (count theList))
--> {1, 7, 13, 19}
[i]Edit: Simplified the code to clarify its working and to remove an “optimisation” that was actually having slightly the opposite effect!
I’ve had a chance to study Vincent’s and mghilissen’s scripts this morning. I hope they won’t mind if I comment here.
Vincent’s script returns the right number of indices, but those returned from lower recursion levels aren’t correct. The value passed to ‘start’ in the recursive calls should be ‘(mid + start)’, not ‘(mid + 1)’.
mghilissen’s script is based on the Quicksort algorithm and is actually a series of converging linear searches that find the first instance of the value, then the last, then the second, then the second-to-last, and so on. For this reason, it’s slightly slower than a single linear search straight through the list. The two recursive calls at the end contribute nothing to the final result but add a terrific amount to the running time.
Binary searches are only effective “ and are only necessary “ because AppleScript’s a “high level” language. The ‘is in’ command actually carries out a linear search itself, but at a lower coding level. This is much faster than using high-level AppleScript commands to carry out the individual details of a linear search. (In much the same way, a person will walk across the room much faster if you tell them to walk across the room than if you give them individual instructions for lifting each leg, shifting their weight forward, and falling in a controlled manner back onto the foot of the current leg. There’s probably a similar allegory to do with Government interference and the National Health Service, but I won’t go into that here. 
)[/i]
