資料內(nèi)容:
3、為什么 left = mid + 1,right = mid ?和之前的算法不?樣?
答:這個(gè)很好解釋?zhuān)驗(yàn)槲覀兊摹杆阉鲄^(qū)間」是 [left, right) 左閉右開(kāi),所以當(dāng) nums[mid] 被檢測(cè)之
后,下?步應(yīng)該去 mid 的左側(cè)或者右側(cè)區(qū)間搜索,即 [left, mid) 或 [mid + 1, right)。
4、為什么該算法能夠搜索左側(cè)邊界?
答:關(guān)鍵在于對(duì)于 nums[mid] == target 這種情況的處理:
if (nums[mid] == target)
right = mid;
可?,找到 target 時(shí)不要?即返回,?是縮?「搜索區(qū)間」的上界 right,在區(qū)間 [left, mid) 中繼續(xù)搜
索,即不斷向左收縮,達(dá)到鎖定左側(cè)邊界的?的。
5、為什么返回 left ?不是 right?
答:都是?樣的,因?yàn)?while 終?的條件是 left == right。
6、能不能想辦法把 right 變成 nums.length - 1,也就是繼續(xù)使?兩邊都閉的「搜索區(qū)間」?這樣就可
以和第?種?分搜索在某種程度上統(tǒng)?起來(lái)了。
答:當(dāng)然可以,只要你明?了「搜索區(qū)間」這個(gè)概念,就能有效避免漏掉元素,隨便你怎么改都?。下?我
們嚴(yán)格根據(jù)邏輯來(lái)修改:
因?yàn)槟?要讓搜索區(qū)間兩端都閉,所以 right 應(yīng)該初始化為 nums.length - 1,while 的終?條件應(yīng)該是
left == right + 1,也就是其中應(yīng)該? <=: