Binary Search 二分搜尋法

Binary Search 大概是很多人學習演算法的入門題(或是 Bubble Sort?),Binary Search 的觀念很簡單,透過每次減半搜尋空間來達到 O(logN) 的時間複雜度,但其細節和變形的用法確非常多。
實作上只要一個邊界設錯,結果就會大不同。刷題的時候總是讓人覺得很煩燥。但只要題目要求搜尋要比 O(N) 快,幾乎是肯定一定要實作 Binary Search 了。

基本用法

最基礎的 Binary Search 用法,程式碼如下。
如果有找到則回傳 index,沒有的話回傳 -1(回傳 left 則是最接近的位置)。

參考題目:LeetCode - 35. Search Insert Position

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while (l <= r) {
int mid = l + (r-l)/2;
if(nums[mid] > target) {
r = mid-1;
} else if(nums[mid] < target) {
l = mid+1;
} else {
return mid;
}
}
return l;
}
};
閱讀全文

Binary Tree Traversal 的方法

Binary Tree Traversal

眾所周知,Binary Tree Traversal 有三種方式,In-Order(中序法)、Pre-Order(前序法)與 Post-Order(後序法)。他們的差異主要是尋訪時,父節點相對於子節點的順序。

閱讀全文

終結永恆,從此無限《永恆的終結》

今年四月,鸚鵡螺出版了艾西莫夫的經典中篇小說《永恆的終結》(The End of Eternity),我很是興奮。長久以來,出版社都只顧著出版名氣最大的《機器人系列》(Robot Series)、《銀河帝國三部曲》(The Galactic Empire Trilogy)與《基地系列》(The Foundation Series),艾西莫夫的作品中也屬這大基地系列最出名。然而,大師之所以為大師,便在於出色的不僅僅是長篇,中短篇也是極為優秀,讀來韻味無窮。例如《神們自己》(The Gods Themselves)、最後的問題(The Last Question)以及這次介紹的《永恆的終結》

閱讀全文

過度思考表象的現代社會《守門員的焦慮》

前一陣子在逛誠品時,偶然看到木馬文化新譯了兩本 2019 年諾貝爾文學獎得主 Peter Handke 的作品《守門員的焦慮》以及《夢外之悲》。藉著這個機會,原本要買赫拉巴爾作品的我,改買了《守門員的焦慮》。

閱讀全文

ETW 介紹 2 - Consumer

前一篇文章介紹了 ETW 和簡單的使用方式,這次我們要加入 Consumer,使得我們可以即時接收事件。

閱讀全文

ETW 介紹 - 以 Event Tracing Session 為範例

因為工作需求,開始接觸 Windows System Programming,每次都覺得 MSDN 寫的很混亂,有時候太注重細節,對於系統沒有全面性的介紹;有時又只有概論,沒有程式碼或實作內容;有些甚至把不同的文件連結在一起就結束了。即使是 Google 找到的資料也比日本製的壓縮機還稀少。最後只能花時間慢慢測試,聽部門的人說,有好幾次都是他們自己試出很 tricky 的用法,跟微軟的技術人員聊一聊,結果居然變成 MSDN 的內容,不知道該哭還是笑。

閱讀全文

如何用WinDBG掛VMware

Steps

  1. Install a Windows System in VMWare
  2. Delete the Printer and add a new Serial Port
  3. Add a shortcut of WinDBG.
  • Edit the target to C:\Program Files (x86)\Windows Kits\10\Debuggers\x64\windbg.exe” -k com:port=.\pipe\com_1,baud=115200,pipe
  • Run as Administrator
  1. Open GuestOS in VMWare, open CMD as Administrator
  • The {ID} is generated by second command
    • bcdedit /dbgsettings serial baudrate:115200 debugport:1
    • bcdedit /copy {current} /d DebugEntry
    • bcdedit /displayorder {current} {ID}
    • bbcdedit /debug {ID} ON
閱讀全文