Binary Search with Burst Condition Code Pattern


  • 0
    X

    I think it's helpful if you use this to program the problems which require you to remember the last valid value or index of a sorted array. And if you can think in this way, it will also remind you to quickly identify a problem as a binary search problem.

    class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            if (nums.empty()) return 0;
            // of course you can use [left] as the valid idx, 
            // but making an additional helps a lot and won't hurt. 
            int last_valid_idx = -1;    
            int left = 0, right = nums.size()-1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                    last_valid_idx = mid;
                } else if (target < nums[mid]) {
                    right = mid - 1;
                } else {
                    return mid;
                }
            }
            // +1 is the place that you want to insert.
            return  last_valid_idx + 1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.