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

Binary search, differently ordered

Shin shared a variation of binary search problem with me yesterday, which was later discovered to be a variation of an exercise from van Gasteren and Feijen's note The Binary Search Revisited cited by Shin's blog post A Survey of Binary Search. The problem: if an array a0, a1, ..., an-1 is rotated from an ordered array ai+1, ai+2, ..., an-1, a0, a1, ..., ai for some i (so a "dip" is present in the array, namely the difference between ai and ai+1), can we still perform binary search on it? Here I try to record the path of thought I've taken.

As described by Shin, the general binary search algorithm assumes an invariant Φ(i, j) holds initially for the entire array, i.e., Φ(0, n-1) is true. And then the loop pulls i and j closer and closer, until j = i + 1. In the case of standard binary search, Φ(i, j) := ai ≤ k < aj where k is the key value to be searched for. Note that Φ(0, n-1) must hold initially but the key may well not be in the array. To fix this, we add -∞ and ∞ to both ends of the array. After the loop, we have ai equals to k if and only if k is present in the array.

Since it was hinted that binary search may be applicable, I looked at the original binary search and tried to find similarities, hoping to discover a suitable way of generalisation. In the case a0 < an-1, we know k is bounded by a0 and an-1, i.e., k is in the interval [a0, an-1]. For the other case a0 ≥ an-1, we know k can only be larger than a0 or smaller than an-1, i.e., k is in [a0, ∞) ∪ (-∞, an-1]. Also observe that performing the original binary search naively is not right. For example, when the median value am is less than k, it does not necessarily mean we should assign m to i --- consider the case when k is located at the left of the dip and am at the right. The way of comparison seems a lot more complicated.

And then it occurred to me that it would be great if [a0, ∞) ∪ (-∞, an-1] can be viewed in the same way as an ordinary interval, so we may still intuitively see the interval shrink as the loop progresses, like the standard binary search. This required gluing the two sides of the real line to an added point ∞, so a circle is formed. The interval in question is then contiguous on the circle, containing the added point ∞. I was introduced to this concept in the undergraduate algebra course taken in my fourth year, which is called the real projective line and amounts to the one-point compactification of the real line. The odd comparison rules all suddenly make sense under this view. While in general numbers on the real projective line do not have a natural ordering, in our case we can say informally that the magnitude of a number x is the minimum distance we travel counterclockwise on the circle from a0 to x, and that a number is smaller if its magnitude is smaller. This essentially cuts the real projective line at a0 and forms a closed ray roughly like [a0, a0-), a0- serving as the new infinity. Walking from a0 towards the infinity on [a0, a0-) is equivalent to walking counterclockwise on the real projective line from a0 and never reaching it again. We can say that the value domain is also rotated: rotating the array indices disrupts orderedness of the array, but we can rotate the value domain correspondingly to make the array ordered again. (I wish I could make this statement more topological! I believe it's something related to the torus.) Comparison under this ordering is simple: if two numbers are on the same side of the dip (which can be determined by comparing them with a0), then perform the usual comparison; otherwise, whichever on the right side of the dip is larger. The binary search algorithm doesn't have to be altered except for changing the way of comparison. We still have to insert a guard a0- as the rightmost element of the array, but there is only one guard instead of two. Notice that this works for binary search on an ordinarily-ordered array as well: values smaller than a0 are greater than all elements in the array under the new ordering, so searching for a value too small simply moves i towards n and -∞ is not needed to guard the left end of the array.

This ordering is my final version, though, which means there were some other versions. For example, I had used an ordering depending on both a0 and an-1 and treated all values from an-1 to a0 (both ends exclusive) as -∞. This resulted in much more complicated case analysis in the definition of the ordering. I had even made a mistake regarding the sign as essential for the comparison, not noticing that topologically 0 did not have a special role on the projective real line. This mistake made me temporarily think that modelling the situation with the real projective line was flawed. But later I discovered there is a cleaner and correct way to utilise the real projective line, which is, well, described above.

However, there is one last serious flaw. If an ordered array is rotated such that a0 = an-1, it should be considered legal input but does not count as ascending under the new ordering! I spotted this seemly-unfixable flaw at midnight, which deprived me of sleep for some two hours. And indeed it is not fixable but it is not a problem about the ordering! Say the two ends of the rotated array have value v. If the median value is also v, then we have no way to decide whether the key value is in the left segment or the right one --- the key can be in any one of them. This observation can even be developed into a full adversary argument, showing that no algorithm can correctly solve the search problem on these arrays in sub-linear time, by arguing any correct algorithm must examine the middle n-2 values of the array and therefore take Ω(n) time: Given an algorithm A and a key k, consider the "flat sequences" consisting of n copies of a number not equal to k. If A does not have to look at all n-2 values in the middle, then (for all but finitely many n's) A does not look at some value at index αn, which means changing the value at αn does not affect the output of A, namely A would still say the key is not found as it would for the flat sequences. Now change the value at αn to k for every flat sequence of length n and feed this set of input to A. Its output must be incorrect. Thus it's not possible to perform binary search, which takes O(log n) time, to correctly determine whether a value is present in this kind of arrays, which takes at least Ω(n) time. It is interesting to see that a naive-looking equality can dramatically increase a seemly-simple problem's complexity.

--
It's been quite a while since I wrote something this long last time, especially in English...

---

A sequel to this post has been posted, which is on whether implementing this new ordering gives a better algorithm than the usual two-pass algorithm in terms of number of comparisons.

Bakery Algorithm

今天 OS 講到 mutual exclusion。暑假 FLOLAC 的 Deductive Program Verification 課堂上，資管系的蔡益坤老師活靈活現地描述 bakery algorithm 的三段峰迴。很可惜我當時仗著有錄音檔，沒把詳細內容寫在 blog 上，後來發現竟然弄丟了兩天的錄音檔，現在只記得其中兩段 XD。

在另一門課 Model Checking 裡面，王柏堯老師用 Spin 抓到一般實作出來的 bakery algorithm 的 bug。蔡老師於是為 bakery algorithm 辯護，要我們注意 bakery algorithm 的前提：號碼牌必須是 unbounded integers！從這裡就可以繼續發展 bounded integer 的變化版，這是第一段峰迴。接著這個峰迴我忘記是第二段還是第三段了：bakery algorithm 不要求從硬體支援 mutual exclusion，最炫的效果是，別人還在寫自己的號碼牌時我們就去看，以致於看錯了別人的號碼，整個演算法都還是對的！這點 Leslie Lamport 自己是到設計出來、寫完證明之後才發現的。Lamport 說：

I have invented many concurrent algorithms. I feel that I did not invent the bakery algorithm, I discovered it.

可見這個 algorithm 有多神妙。這個演算法出現在〈A New Solution of Dijkstra's Concurrent Programming Problem〉，這篇論文只有三頁。在 Lamport 的個人網頁上有一段說明，即使不看 paper 也應該讀一下那段說明，非常有趣。（剛剛引的句子就是從那段說明引來的。）

--
弄丟這份錄音檔真是一大損失 XD。

---

我在猜我忘記的那段峰迴是 bakery algorithm "[...] allows the system to continue to operate despite the failure of any individual component"，不過不能確定 XD。

Adversary Argument

還是先懺悔：我去年幾乎沒做助教出的 voluntary exercises，只記得有次助教解答有附一份關於 adversary argument 的文件，但那時看沒什麼感覺 XD。

這次為了證明 "double-end problem"（說不定隨機客的一大樂趣就是為問題取名字？XD）的比較次數下界為 3n/2 苦思良久。昨晚十一點多想到說不定可以把它化成圖論問題（因為 "champion problem" 的比較次數下界用 graph connectedness 思考非常直覺），但沒看出什麼性質。接著從 decision tree model 慢慢磨出 adversary argument 的邏輯，但因為我是從圖論的脈絡過來，討論繁複，沒辦法找到足夠簡單的分析方式。後來上網一找發現 "adversary argument" 這詞，才知道是以前不認真，自食惡果 XD。

--
今年就趁機會把隨機客的演算法作業都想一遍吧。（其實是不得不想 ─ 也是自食惡果？XD）

Incompatibility

昨天企圖從隨機客的 little-o 定義推到 CLRS 的定義（反向是 trivial），發現怎麼湊都不對，最後造了一組反例：

則 f(n) = O(g(n)) 且 f(n) \neq \Omega(g(n))，依隨機客的定義就有 f(n) = o(g(n))。但考慮 CLRS 的定義（也就是常見的定義），若取 c = 1/2，則 f(n) > c g(n) infinitely often，不可能在哪個 n_0 之後恆有 f(n) < c g(n)。所以隨機客的定義條件是比較弱的。寫信給隨機客，但他似乎不打算回應… 剛剛想用隨機客的定義反證作業第一題逼隨機客出面，但試了之後發現好像沒辦法，因為 n^2 太正常了（compared with the g(n) above）。

--
真煩，不管了。

---

現在用 Weijin 的帳號貼到隨機板上了。這樣應該很難裝作沒看到？XD

 作者  jimbedb (XD)                                                 看板  hil 
 標題  [問題] little-o 的定義與課本不相容？                                   
 時間  Sun Oct 21 20:57:20 2007                                               
───────────────────────────────────────

老師在 slide 1 p.94 對 f(n) = o(g(n)) 的定義是

    f(n) = O(g(n))    and    f(n) \neq \Omega(g(n))，

而課本在 p.48 的定義（以及查得到的所有其他定義）是

    for any c > 0, there exists n_0 > 0 s.t. f(n) < c g(n) when n > n_0。

第一個定義的條件是比較弱的。若我們令

    f(n) = n，

    g(n) = n      if n is odd
         = 2^n    if n is even，

那麼 f(n) = O(g(n)) 而且 f(n) \neq \Omega(g(n))，所以 f(n) = o(g(n))。
但在第二個定義下，若取 c = 1/2，f(n) 會在奇數點上大於 g(n)/2，而不可能
在某個 n_0 之後使 f(n) < c g(n) 恆成立，因此 f(n) \neq o(g(n))。

所以第一個定義是不是不夠充分呢？

--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.249.77

---

隨機客終於回了！

→ hil:有趣的例子! ;)                                           推 10/21 23:51
→ hil:好像變得有點像哲學問題, 就是這種狀況要不要當作little-o?  推 10/21 23:52
→ hil:為了不要搞混大家, 我們還是維持原來課堂上的定義.          推 10/21 23:53
→ hil:畢竟這樣的定義對於「一般」的演算法時間複雜度的函數是OK的 推 10/21 23:53
→ hil:「隨機客」明年再改成課本那樣好了..                       推 10/21 23:54
→ hil:Good job!! (or nice boat? ;)                             推 10/21 23:55

--
所以真的沒收到我的信嗎…？