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