二分法模板的思考——LeetCode35

原題如下:

二分法模板的思考——LeetCode35

其實很簡單,二分法就搞定了,但是我看到題解裡面有人說有二分模板,是這樣的:

二分法模板的思考——LeetCode35

下面是他對這道題的解法:

二分法模板的思考——LeetCode35


下面我想記錄的是兩個問題:

1、為什麼條件判斷是left<=right

2、為什麼最後返回left就可以了

我認為是這樣子的:

二分查找最後會糾結的無非是下面這兩種情況:

二分法模板的思考——LeetCode35


二分法模板的思考——LeetCode35

在思考時,要記住的點是,(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就是插入位置。

考慮清楚這兩種情況,對於題解中講述的這種模板也就清楚了。

歡迎討論


分享到:


相關文章: