這道題比較巧妙的是末尾位置的計算糜颠,他用的是找比target大1的位置,然后這個位置-1就得到了target的最后一個位置萧求。
為了支持這個其兴,所以二分查找哪里也是有所不同的,首先默認是找最左面的位置夸政,所以要在要在左面的閉區(qū)間里面找元旬,所以r=m不能減一;再說右邊界的初始值的問題守问,因為有可能target這個值是在最后匀归,這樣的話,我們按照之前的二分查找耗帕,將長度減一的話穆端,我們得到的就是長度減一的返回,那last本來還需要減一的仿便,所以就會有問題体啰。其他的話,就是正常的二分查找了嗽仪。最后返回結果之前記得判斷一下是否沒有找到荒勇。
代碼:
https://github.com/hanleirx/LeetCode/blob/master/34.%20%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9F%A5%E6%89%BE%E5%85%83%E7%B4%A0%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%92%8C%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE