Template & Tips

binary search 概念是, 要找左半部還是右半部？

三分法 use left <= left

二分法 use left < left

1. 找模糊值 first or last occurrence, 二分法

see leetcode 34

        int left = 0;
        int right = nums.length - 1;
        // find first occurrence
        while (left < right) {
            int mid = left + (right - left)/2;

            if (nums[mid] < target) { // 往右半部找
                left = mid + 1;
            } else { // 往左半部找
                right = mid;
            }
        }
        return left; // right
        
        // find last occurrence
        while (left  < right) {
            int mid = left + (right - left + 1)/2; // notice! +1

            if (nums[mid] > target) { // 往左半部找
                right = mid - 1;
            } else { // 往右半部找
                left = mid;
            }
        }
        return left;

2. 找確切值, 三分法, template,

left, right = 0, len(array) - 1 
while left <= right: 
    // (left + right) >>> 1 is best!
	  mid = (left + right) >>> 1    // left + (right - left) / 2 
	  if array[mid] == target: 
		    # find the target!! 
		    break or return result 
	  elif array[mid] < target: 
		    left = mid + 1 
	  else: 
		    right = mid - 1

1. when do you use while (start < end) , when do you use while (start <= end) ?

You use while (start <= end) if you are returning the match from inside the loop.

You use while (start < end) if you want to exit out of the loop first, and then use the result of start or end to return the match.

可以參考這篇的思路：

https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

3. 找最近似值 (closet to ...)

        int left = 0;
        int right = nums.length - 1;
        // find first occurrence
        while (left + 1 < right) {
            int mid = (left + right) >>> 1; 

            if (nums[mid] < target) { // 往右半部找
                left = mid;
            } else { // 往左半部找
                right = mid;
            }
        }
        if (nums[right] < target) { // right < target , target 最大 
            return right;
        } else if (nums[left] > target) { //  target  < left  , target 最小
            return left;
        } else { // left < target < right ,  target 介於中間
            return (target - nums[left] < nums[right] - target) ? left : right;
        }
        

find peak (162)

if (nums[mid] < nums[mid+1]) {
    left = mid + 1;
} else {
    right = mid;
}

Rotated

            while (left <= right) ...
            
            // duplicate 多這個條件
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target <= nums[mid]) { // in left
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
                    
            } else {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }

Mini in Rotated

if (nums[mid] > nums[right]) {
    left = mid + 1;
} else {
    right = mid;
}

// duplicate
if (nums[mid] > nums[right]) {
    left = mid + 1;
} else if (nums[mid] < nums[right]) {
    right = mid;
} else { // nums[mid] == nums[right] .=> add this 
    right--;
}

二分法

二分查找 tips

decrease and conquer template

原始 binary search 寫法分成三部分

另一種做法

decrease and conquer, 朝排除 mid 思考, 分為兩部份

while(left < right) 這樣寫退出時, left == right, 所以回 left or right 都可以

根據邊界收縮,中間值要考慮 只有兩個元素時, [0, 1] => mid = (0+1)/2 = 0, 永遠取不到右中位數

上取整可以解決

如果題目說搜索區間必定有 target, 就ok 但如果可能是會找不到的, 就不是一定要回傳 nums[left], nums[right]

根據什麼時候狀況不是解, 寫if, if對 else 自然對

第二解, 因為可以插入在最後, 所以可以不用特別判斷, 所以 右邊界 可以改成 len

第三解, 因為看到目標元素, 就達成題目要的, 所以可以多一個 == 的挑件判斷直接返回答案