### 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 ≼which is complex to implement. After some simplifications, however, it reduces to_{A}y ≡ (((x ≥ A ∧ y ≥ A) ∨ (x < A ∧ y < A)) ∧ x ≤ y) ∨ (x ≥ A ∧ y < A),

x ≼which says_{A}y ≡ (x ≥ A ∧ x ≤ y) ∨ (x ≥ A ∧ y < A) ∨ (x ≤ y ∧ y < A),

`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 `a`_{m} ≼_{a0} k

, it seems we still have to perform 3 comparisons in the worse cases. Note, however, that `k`

and `a`_{0}

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 ≼which says that to assert_{A}y ≡ (y < a∧ (x ≥ a ∨ x ≤ y)) ∨ (¬(y < a)∧ (x ≥ a ∧ x ≤ y)),

`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)...

Labels: Algorithms

<< 回到主頁