while(i+1 < j)模板不可用的情形

标准while(left + 1 < right)的模板

• 没有if (nums[mid]==target)的early return

• 只有if () else ()两种情况，绝对的二分条件

• 没有if() else if () else ()的3分或者更多的情况，这也是为什么median of 2 sorted arrays不能用这个模板的原因

//pre-processinng
...
left = 0, right = len - 1;
while (left + 1 < right) {
    mid = left + (right - left) / 2;
    if (nums[mid] <target) {
        left = mid;
    } else {
        right = mid;
    }
}
...
//left + 1 == right
//2 more candidates
//post-processing

while (left + 1 < right)不可用的情形

发现的规律：

1. 这些题目都是运用了binary search的思想，但不是直接能从nums[left], nums[right]里找到result

2. 如果是纯 binary search的题目， 的确while(left + 1 < right)更无脑，不会写出bug

• median of two sorted array

• Koko Eating bananas

• Find the smallest divisor Given a Threshold

Leetcode总结的binary search3种模板

Explore - LeetCodeLeetCode

while (left + 1 < right) 可用的前提：最终结果一定在nums[left] or nums[right]中间

如果第1条不能满足，可以考虑while(left <=right)的模板

//pre-processinng
...
left = 0, right = len - 1;
while (left <= right) {
    mid = left + (right - left) / 2;
    if (nums[mid]==target) {
        return mid;
    } else if (nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
...
//right + 1 == left
//No more candidates

Search Insert Position

• 一道简单的binary search来体会 while (left + 1 < right)的标准模板和改进模板的区别

//标准while (left + 1 < right)模板
public int searchInsert(int[] nums, int target) {
        int begin = 0, end = nums.length - 1;
        if (nums[end] < target) return end + 1; //edge case[1,3,5,6] 7
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            if (nums[mid] <= target) {
                begin = mid;
            } else {
                end = mid;
            }
        }
        if (nums[begin] >= target) return begin;
        return end;
}

//改进
public int searchInsert(int[] nums, int target) {
        int begin = 0, end = nums.length - 1;
        if (nums[end] < target) return end + 1; //edge case[1,3,5,6] 7
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                begin = mid;
            } else {
                end = mid;
            }
        }
        if (nums[begin] >= target) return begin;
        return end;
}