LeetCode短影片 | 以後要求時間複雜度log的一定就是二分演算法了

• 2019 年 12 月 23 日
• 筆記

接下來繼續做二分查找的演算法，看下面圖片，我們第4題號已經做完了，參考這裡。

然後我看了第29題，好像有點難，暫時就不做了。接著就做下面一道『搜索旋轉排序數組』。

題目：

而對於我們要找的target，target不在的那一段，所有數字可以看做無窮大，這樣整個數組就可以看做有序的了，可以用正常的二分法去找 target 了，例如：

[ 4 5 6 7 1 2 3] ，如果 target = 5，那麼數組可以看做 [ 4 5 6 7 inf infinf ]。

[ 4 5 6 7 1 2 3] ，如果 target = 2，那麼數組可以看做 [ -inf -inf – inf -inf 1 2 3]。

和解法一一樣，我們每次只關心 mid 的值，所以 mid 要麼就是 nums [ mid ]，要麼就是 inf 或者 -inf。

什麼時候是nums [ mid ] 呢？

當nums [ mid ] 和 target 在同一段裡邊。

怎麼判斷nums [ mid ] 和 target 在同一段？

把nums [ mid ] 和 target 同時與 nums [ 0 ] 比較，如果它倆都大於 nums [ 0 ] 或者都小於 nums [ 0 ]，那麼就代表它倆在同一段。例如

[ 4 5 6 7 1 2 3]，如果 target = 5，此時數組看做 [ 4 5 6 7 inf infinf ]。nums [ mid ] = 7，target > nums [ 0 ]，nums [ mid ] > nums [ 0 ]，所以它們在同一段 nums [ mid ] = 7，不用變化。

怎麼判斷nums [ mid ] 和 target 不在同一段？

把nums [ mid ] 和 target 同時與 nums [ 0 ] 比較，如果它倆一個大於 nums [ 0 ] 一個小於 nums [ 0 ]，那麼就代表它倆不在同一段。例如

[ 4 5 6 7 1 2 3]，如果 target = 2，此時數組看做 [ – inf – inf – inf – inf 1 2 3]。nums [ mid ] = 7，target < nums [ 0 ]，nums [ mid ] > nums [ 0 ]，一個大於，一個小於，所以它們不在同一段 nums [ mid ] = – inf，變成了負無窮大。

執行過程貼影片，請欣賞！

貼程式碼

——END——