又開一個新系列。
我高中、大學都是純文組，物理化學很差，微積分迄今不會。(但真的也完全不影響成為軟體工程師。)
大四下決定轉資工前，沒寫過一行code，如今卻在美國一線大廠擔任軟體工程師。我相信這個系列，能更貼近文科生學程式時，會遇到的所有坑。(市面上比較少看到類似教材。但雖然說寫給文組生，所有人都適用啦。)
本系列想以寫程式最核心的Data Structure & Algorithm做骨幹，過程帶入寫程式的方式、技巧。希望看完這個系列後，你能一次學齊寫程式所有需具備的知識。(Data Structure & Algorithm是我認為學校課程中，“唯一”跟業界相關的科目。寫程式、刷題、找實習、找正職、跳槽等等，一定都會用到。)
我的預期是，讓一個零程式基礎的文科生，能一路從“零基礎轉資工” -> “寫給文組生的程式教學” -> “我要拿大廠offer!“ -> “帶你刷Leetcode“，獲得在美國大廠工作的所有前置知識，有興趣來美國工作的歡迎參考。(有餘力的話，我也想錄些影片，帶大家實際做Project。)
上集，我們來介紹寫程式的本質、Binary Search的概念。
下集，透過完整程式碼輔助，介紹程式語言裡的Data types、Data Structure，及分析我每行Binary Search程式碼的用途。
進入正題。
大家想到寫程式，可能瞬間浮現的畫面：一個人孤單對著電腦，畫面充滿看不懂的程式碼。這個想像，對、也不對。有些時候，的確找不到Bug時會這樣；但在美國，更多的時候，是一直開會，討論、定義需求。如果大家對這行業，有著只會與電腦打交道的刻板印象，我只能說，至少在美國不會是如此。(我一天至少開四個會，幾乎半天時間都在開會。)
接著我們來探討，寫程式的本質到底是什麼？對我而言，我的定義是：“通過可運行邏輯，逼近、甚至完全擬合現實世界的建模。”
實際用途上舉例：我現在想像，路上的車好多，但計程車好少，對於沒車的人，能不能有種媒合的手段，讓有車的人充當司機，沒車的人可以隨時叫車。（就uber啦）
此時就會有無數次的討論、定義需求，嘗試逼近、最佳化我們的想像。
如，顧客媒合車的時候，是周遭任意一台，還是離顧客最近的一台。最近的一台，指的是物理距離最近，還是開到顧客身處位置最快。遲遲沒抵達，顧客能不能取消訂單。遲遲的定義是什麼，具體是幾分鐘。依照高峰、非高峰時段，是不是定義又會有差別。高峰期具體又是什麼時候、平假日有差嗎？另，有些顧客想媒合高級一點的車，能不能做到，等等，無數的問題。
思考這些問題的過程，都是盡量讓我們的邏輯，能越逼近現實越好。而這些討論、及寫Design document來論述怎麼實踐、哪種實踐方式更好，才是我認為軟體工程師的價值所在。而寫程式本身，僅僅只是把討論的結果，寫成一段段可運行的邏輯，進而達成目的。
(附帶一提，有時候邏輯沒考慮周全，會有奇怪的運行結果，這個我們叫bug。之後就要花時間debug，也是寫程式比較困難的一個地方，因為很多時候就是找不到問題。就是會有思維盲點 — — 明明感覺都符合邏輯，但為什麼就是某些情境會有奇怪的結果。）
核心功能順利實踐後，後續則會持續維護、最佳化現有功能。如，周遭距離有1000台車，我們怎麼更快計算出哪台適合消費者；早晚高峰可不可以通過大筆資料做輔助，讓我們更好推估早晚高峰的時間點，甚至未來由電腦自行計算。
也可以基於現有用途，開發新功能。如，有些車沒人媒合時，能不能做其他事，能不能幫忙運送顧客訂的餐點。(現在美國甚至可以直接讓uber司機送包裹到別人家，不知道台灣有沒有。疫情期間我就試過，讓司機運幾本教科書給我住比較遠的同學。在同一個城市的情況下，比Fedex方便多了。)
學術界的程式碼也符合我的定義。由於走在學術理論的最前沿，我們並不知道寫出來的程序，是不是符合這世界的實際運行規則，只能不斷修改、觀察修改後的結果，來試圖逼近“造物主”的法則。
落落長講這大段，有幾點用意：
1. 只教些程式語言的語法，會有點捨本逐末，畢竟寫程式的目的，是要解決問題，做出擬合世界的建模。所以本系列會更強調Algorithm、及一些寫程式的思維。
2. 可以解釋為什麼寫程式在未來不至於找不到工作。現代社會，還有太多產業，可以透過寫程式的方式，自動化、現代化既有流程；任何腦中的想法，只要實踐的出來，都有機會讓人類既有的生活變更好。(Computer Science也才出現不到百年，人類社會還有太多的痛點等著被發掘、進而成為一門生意。)
3. 承接上一點，只要自己coding能力夠強，任何腦中的想法，都能成為可運行的程式，進而讓想像成為現實。這也是對我來說，資工領域最有魅力的事。（以前在文組時，我固然很贊同開放性論點的討論，但有時也有點厭倦誰也說服不了誰的感覺。更多的時候是：我知道你說的對，但我就是不認同。相較起來，寫程式是討論時，雙方觀點不一致，我們就都寫寫看，運行看看。哪個方式好，拿結果一比就知道，沒有模糊的空間，也不用言語上無止盡的交鋒。）
接著進入Binary Search的部分。Binary Search是Algorithm的一種。Algorithm在台灣翻作演算法、中國翻作算法，簡稱Algo。我會這樣定義Algorithm：“解決一個問題時，所需要的步驟”，你要理解成SOP也行啦。而這裡的步驟，當然是越有效率越好。（如果不管效率，那就不需要這門學科了。畢竟達成目標的方法千百種。）
直接舉例最快。
現在玩一個遊戲：1000名參加者背對你站成一橫排，背上貼著不公開的背號，他們的站位依背號“由小到大”排序(號碼連不連號不影響)。請問最差的狀況，花幾次能找到477號 or 知道477號不在所有參加者中？停下來想一下。
最直覺的方式就是從第一個參加者開始，一個個撕下他們的背號，確認是不是477。第一個1號，第二個人8號，第三個人13號等，一路看下去。因為他們的號碼不一定是連號，所以我們也不能隨意跳號檢查。(說不定第四個人就是477。)
以477的例子，最好情況下，第一個人就是477號，只需要一次。最差情況下，剛好所有人都是連號，就得玩477次。
想倒著數回來也隨意。但在玩多次的情況下，我們極端最差時，得玩1000次，才能找到X號、或知道X號根本不存在參加者中。(舉例：號碼是一個不存在的1547號，但我們選擇從第一個人開始數，數到第1000人，發現他背號也就1200。)
這種方式叫Linear Search（線性搜尋)，是一種效率不高的Algorithm。Algorithm的步驟為：
1. 選定一個方向，正的或逆的。（不是必須步驟，其實不用寫在Algorithm裡。）
2. 撕背號，比對結果。
3. 找到目標背號，結束；沒找到，回到第二步，直到撕完所有人背號停止。
Linear Search的Time Complexity(時間複雜度)，是O(n)。Time Complexity是Algorithm學科發明的概念，因為想有一個統一標準，衡量不同方法，哪個比較好，以免各說各話。時間複雜度越低，當然也就越好。O(n)以人話理解就是：最差情況下，我們程式得運行n次。最差情況，演算法科學家定義用O這個字母來代替，不然每次寫Worst Case(n)太麻煩了；n則是指總數。(例子是1000人，最差就1000次；例子是n人，最差就是n次。)
另，實際分析Time Compextity時，都是在分析最壞狀況，而不是最好狀況Ω。(是的，這個符號也是演算法科學家所定義，意思是最好情況。在我看來，這只是要增加理論完備性，除了上課以外，實際分析時用不到。不然在最好狀況時，什麼方法都是1次就能找到 — Ω(1)，沒什麼參考意義。)
Time Complexity是非常重要的概念，在面試的時候，寫完任何code，面試官一定都會問你，你這段程式碼的Time Complexity是什麼。
上述例子，我們可以發現，這個隊伍有個特性：有序。運用這個特性，演算法科學家發現更有效率的Algorithm — — Binary Search。Binary Search，中文翻二元搜索，這個Algorithm的核心概念很直覺：往中找。我們每次都直接找現有隊伍中，最中間的那個人。
繼續回到例子，我們第一次就直接撕第500人的背號，假如這個人的背號比477號小，雖然我不知道前面499人的背號是些什麼，但無所謂，在有序的特性下，連第500人都比477號小了，那前面499個人，肯定也如此。我們只比一次，就篩掉了500人。剩下500人中，我們再找中間，又可以一次篩掉一半，以此類推。Binary在這的意思，就是我們每次都能透過正中間的人，把隊伍分成兩堆(二元)。
這個Algorithm的步驟為：
1. 挑隊伍最中間的人。
2. 撕背號，比對結果。
3. 找到目標背號，結束；沒找到，如果中間人的背號比目標大，則找這個人以前的隊伍；反之找這個人以後的隊伍。回到第一步，直到剩一個人停止。
(分析清楚後，寫程式，也就只是把這個Algorithm，用程式語言的語法打出來而已。再再強調，我們到底要打些什麼，才是最重要的。)
不可免俗的討論時間複雜度。每次都篩一半，如果是4人的隊伍，會是 4 -> 2 -> 1，最差情況玩兩次。16人的隊伍，16 -> 8 -> 4 -> 2 -> 1，四次。有沒有發現，這就是以2為底的log。(Algorithm的世界，底沒特別講，都預設為2。來複習一下log：底為2的情況下，log4的意思，就是在說2的幾次方會是4，也就是2；log100，就是在說2的幾次方會是100，答案是6.64；log n以此類推，2的幾次方會是n。)
所以n人的隊伍，每次篩一半人，最差情況要撕幾次背號？這就等價於2的幾次方等於n。因此，這裡的Time Complexity就是O(log n)。可能有人好奇n跟log n差別大嗎？ 如果隊伍是2的10次方，1024人，Linear Search最差就是找1024次，Binary Search最差則是找10次，大家可能覺得差不多。但數字再大一點呢？假如全世界的人都來玩，前者最差是找78億次，後者只需要log(78億)次，等於32次。
平常寫程式時，能不能寫出時間複雜度低一點的方法，也是決定好工程師、普通工程師的關鍵點之一。這同時是大家平常刷題時，最需要花時間的地方。如果只要求寫出如Linear Search的暴力解(暴力解英文叫Brute-force)，其實都很好寫。(面試時，通常一題要寫好幾種寫法。因為一種方法寫完後，面試官會說，還有沒有更好的方法，能進一步降低時間複雜度。一般就是從暴力解，一路寫到最優解。)
(難得設計圖片，就獻給這次啦。文章有任何疑問的地方，請直接公開留言，大家的問題應該都差不多。我會盡我能力幫助大家理解。)
