Binary search, differently ordered (II)

(This is a sequel to Binary search, differently ordered.)

An important question about the new ordering raised by Shin: just how efficient can this new ordering be implemented? The formula I wrote down for the ordering was

x ≼A y  ≡
  (((x ≥ A ∧ y ≥ A) ∨ (x < A ∧ y < A)) ∧ x ≤ y) ∨ (x ≥ A ∧ y < A),

which is complex to implement. After some simplifications, however, it reduces to

x ≼A y  ≡
  (x ≥ A ∧ x ≤ y) ∨ (x ≥ A ∧ y < A) ∨ (x ≤ y ∧ y < A),

which says x ≼A y holds exactly when two of the three conditions x ≥ A, x ≤ y, and y < A hold. Although in each run of the loop we need only determine whether am ≼a0 k, it seems we still have to perform 3 comparisons in the worse cases. Note, however, that k and a0 are fixed throughout the loop, and indeed fixed from right beginning of the program. So in fact we need at most 2 comparisons for each run of the loop instead of 3. To be more precise, the definition of the ordering can be transformed into

x ≼A y  ≡
  (y < a ∧ (x ≥ a ∨ x ≤ y))  ∨  (¬(y < a) ∧ (x ≥ a ∧ x ≤ y)),

which says that to assert x ≼A y we require only one of x ≥ a and x ≤ y to be true if y < a, or both if ¬(y < a). As Shin pointed out in his comment, the usual solution to this problem is running binary search twice, which requires 2 lg n comparisons. So our one-pass algorithm is no worse than the two-pass approach in terms of number of comparisons. For now I can't think of a way to decrease the constant 2, though, neither can I prove that we need at least 2 lg n comparisons for this problem.

--
However I believe it is time to consider this problem closed (to some extent)...