How can a string be neither less than another string nor greater than another string, but still not equal to that other string?
Something weird with references perhaps? Like ‘<’ and ‘>’ automatically dereferencing references, but ‘=’ not doing so, so perhaps in the ‘<’ or ‘>’ case actual string values are being compared, but in the ‘=’ case it’s the equality of two references or a reference and a dereferenced object that’s the issue?
Below is a simple binary search, as I originally wrote it:
on findByKey(a, k)
local l, r, m, k2
set l to 1
set r to length of a
considering case
repeat while l <= r
set m to (l + r) div 2
set k2 to item 1 of item m of a
if (k = k2) then
return item m of a
else if (k > k2) then
set l to m + 1
else
set r to m - 1
end if
end repeat
end considering
return missing value
end findByKey
The only important difference between this and a basic binary search is that the search is done on a sorted list of lists, with the first item in each list being the sort key.
I did some initial testing of the above code, and it seemed to work fine, but then in actual use I kept getting “missing value” back for things which I knew should have been found. I added some log statements for debugging, and what I saw was strange: the algorithm was successfully converging on the correct matching item, but when it had the match in hand, and was comparing two completely identical looking strings (Unicode text, actually… I made sure that the search key and the stored keys were all of class Unicode text), the ‘=’ operation declared that the two strings were not equal, causing the binary search to keep looking, even after finding the right match, until it failed.
Changing the code as I did below, to explicitly test both ‘<’ and ‘>’, and leaving equality as what’s left over when the first two comparisons fail, fixed the code. So I have a solution, but I’m left scratching my head as to why this fix was needed.
on findByKey(a, k)
local l, r, m, k2
set l to 1
set r to length of a
considering case
repeat while l <= r
set m to (l + r) div 2
set k2 to item 1 of item m of a
if (k < k2) then
set r to m - 1
else if (k > k2) then
set l to m + 1
else
return item m of a
end if
end repeat
end considering
return missing value
end findByKey