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

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--;
}