原題如下:
其實很簡單,二分法就搞定了,但是我看到題解裡面有人說有二分模板,是這樣的:
下面是他對這道題的解法:
下面我想記錄的是兩個問題:
1、為什麼條件判斷是left<=right
2、為什麼最後返回left就可以了
我認為是這樣子的:
二分查找最後會糾結的無非是下面這兩種情況:
在思考時,要記住的點是,(L+R)/2在這種鄰近的情況下,
mid是等於L的。對於第一種情況,
第一次循環,**由於在判斷時,先判斷的L**,所以L會mid+1,也就是變成R。
第二次循環,L,R重合了,L不會被觸發,反而是R會 -1,變到剛才的L位置。 至此,while循環結束。
返回L就是插入位置。
對於第二種情況,
第一次,L會 +1,和R重合。
第二次,L會+1,超過R,while結束。
返回L就是插入位置。
考慮清楚這兩種情況,對於題解中講述的這種模板也就清楚了。
歡迎討論。
閱讀更多 QXcoding 的文章