推 mathtsai: 1.設計演算法不是要你寫程式09/02 01:11
→ mathtsai: 沒有人喜歡看程式 應該用文字&圖 說明你的方法09/02 01:12
原來如此@@！之前不知道
→ mathtsai: 2.你的寫法是錯的 舉例 7 8 1 2 3 4 5 609/02 01:13
→ mathtsai: 1<2 但是你卻會去找右半邊 這樣是不對的09/02 01:13
→ mathtsai: 觀察一下每次二分搜的時候會有什麼性質09/02 01:14
→ mathtsai: 這題是十分簡單的題目09/02 01:14
→ mathtsai: 然後啊 如果你的code真的這樣寫 會噴error09/02 01:20
→ mathtsai: 理由是mid-1,mid+1不一定能在Arr的宣告裡面09/02 01:20
瞭解，我原本想說用mod應該就不會了，但剛剛想想其實還是會...orz
→ mathtsai: 應該要加一些邊界判斷之類的 (mid=1,mid=n => 回傳mid)09/02 01:21
請教m大，因為我一開始是卡在沒有key做binary search
剛剛想到，如果我是拿A[low],A[mid],A[high]這三個來做比較不知道是否可行呢？
像是這樣
https://i.imgur.com/bcjYe0U.jpg
→ mistel: 我又忘記加上bound check QQ09/02 07:50
※ 編輯: mistel (114.136.219.48 臺灣), 09/02/2019 07:51:37
→ JKLee: 先把array的頭尾接在一起形成一個環09/02 08:06
→ JKLee: 要把環分開成兩個部分要切斷兩個點09/02 08:06
→ JKLee: 你的演算法23451會出錯09/02 08:10
→ JKLee: 先暫時不要去想array的index。09/02 08:14
→ JKLee: 如果有一個環， 09/02 08:14
→ JKLee: 環上的數字已經sort好了， 09/02 08:14
→ JKLee: 你會怎麼找最大的數字? 09/02 08:14
J大，我知道要找兩個點切割子問題，但我真的想不通要怎麼切才會確定最大的值會在我留
下來的那一塊...
※ 編輯: mistel (114.136.219.48 臺灣), 09/02/2019 12:22:22
→ Ricestone: 你新的想法沒錯吧，就是每次都看這一半正不正常09/02 12:58
→ Ricestone: 差在該怎麼停下來，所以確認mid是不是斷點，斷在左邊還 09/02 13:05
→ Ricestone: 是右邊09/02 13:05
→ mathtsai: 新的一樣是錯的 4 5 1 2 就錯了09/02 13:38
→ mathtsai: 然後你新的寫法一樣是在寫程式 09/02 13:38
→ Ricestone: 就是要先確認斷點啊09/02 13:39
→ mathtsai: 分成一些case寫下來 (1)...(2)...(3)... 09/02 13:42
→ mathtsai: 條列式就能說明你的方法了 教授也一目瞭然 09/02 13:43
→ mathtsai: 這題如果我沒猜錯 元素應該都不能重複 09/02 13:46
→ mathtsai: 不然 1 1 1 1 1 1 1 1 1 5 1 這樣子根本不能二分搜 09/02 13:48
→ mistel: 我懂了，我應該再檢查mid這個點的左右鄰居，確認最大的點 09/02 14:46
→ mistel: 我會記住用這種答題方式答題，感謝m大J大跟R大!!!! 09/02 14:50
→ mathtsai: 不對 你的回答表示你沒有懂 09/02 15:04
我的意思是遞迴的中斷條件修改成：
若中點確實大於左右端點，
那我再檢查中點是否大於左鄰居跟右鄰居，
成立，則中點最大；
否則，若左鄰居比中點大，遞迴搜尋左半邊；
否則，右鄰居大，遞迴搜尋右半邊；
我想法是數列是遞增的，
所以如果中點是最大，那它一定大於端點且大於左右鄰居（代表左半數列跟右半數列都比中
點小），如果中點不是最大，那必然左鄰居跟右鄰居有一個比中點大，我就往那一邊繼續搜
尋
所以我只要兩個條件都成立，這個就是最大 ...
請問這樣子想法還是不對嗎，其實我不知道我到底是方向就錯了還是細節就錯了，請再指點
一下，麻煩了
※ 編輯: mistel (114.136.219.48 臺灣), 09/02/2019 16:51:39
→ mathtsai: 還是不對啊 7 8 1 2 3 4 5 6 這個例子一樣不會過 09/02 19:17
→ mathtsai: 你可以動手舉幾個例子 09/02 19:19
→ mathtsai: 看看最大的在左半和右半的時候 會有什麼樣的性質 09/02 19:20
→ Ricestone: 為什麼又跑回去了？判斷該往哪一半就是你前一個想法啊 09/02 21:19
→ Ricestone: 停止條件就是mid左右有沒有斷點，斷點就是後面比前面小 09/02 21:20
→ Ricestone: 如果到最後都找不到就是沒斷點（也可以一開始就判斷） 09/02 21:21
→ Ricestone: 反正不管是哪個部份，左端比右端小，數列就是正常 09/02 21:26
→ Ricestone: 判斷mid左右有沒有斷點，其實就是在確認子數列的端點有 09/02 21:26
→ Ricestone: 沒有發生斷點 09/02 21:27
→ mistel: 好的，瞭解，要判斷的是mid左右是不是有斷點 09/03 08:44
→ mathtsai: 我覺得"判斷左右"這句 你又要跑去檢查+1,-1了... 09/03 14:13
→ mathtsai: 把數列切半，觀察哪一半有發生左端比右端大的狀況 09/03 14:14
→ mathtsai: 如果左右都沒有這種狀況，代表左右都sort好了 09/03 14:15
→ mathtsai: 那麼左右兩半的右端比較大的就是最大元素 09/03 14:15
→ mathtsai: 哪一半的左端>右端，就繼續遞迴找那一半 09/03 14:16
→ mathtsai: 短短幾句話不就解決了嗎... 09/03 14:17
→ mistel: 真的太菜了QQ我理解這個問題會發生的狀況跟性質了 感謝你 09/03 14:53
→ Ricestone: 檢查斷點跟一次兩子列都檢查是兩種不同的做法而已 09/03 16:24
→ Ricestone: 只是只檢查左子列+判斷左斷點跟一次檢查兩子列的差異 09/03 16:26