one BinarySearch template to AC all the related problem


  • 2
    F

    I used to use the following template to solve the binary search problem, but failed many problems. It is a little bit hard to cover all the corner cases with the below binary search template !

    Here is the template I used to post, I will keep [left, right) left close right open field and keep this property always

            int start=-1, end=n-1;
            while(end-start>1){
                int mid=(start+end)/2;
                if(nums[mid]>=target) end=mid;
                else start=mid;
            }
    

    But I do find this template is not good enough to pass all the problem related to binary search !!! So where is the general template ?

    With the help from my classmates, we finish it !

    It should be like this, there are 3 key points to remember !!!

    • [left, right] left close right close , so your left = left_most_possible value so with right

    • while (left < right) the loop should end when left == right

    • mid = left + (right - left) /2 in this case the middle value is closer to left, so we need to move the left one step while keeping the right = mid in other case. So We can infer the conditions when the left will move one step !!! This is the most import parts, you should ensure that once the condition is satisfied, the left can move one step.

    In summary, I have use this template to solve all the binary search problem set in leetcode !

        int guessNumber(int n) {
            int left = 1, right = n;
            while (right > left) {
                int mid = left + (right - left) / 2;
                int ans = guess(mid);
                if (ans == 1) {
                    left = mid + 1;
                }
                else {
                    right = mid;
                }
            }
            return left;
        }
    
    

    For the purpose you can understand it better, I post the solution to 2 other typical problem :aerial_tramway:

    Problem Find Minimum in Rotated Sorted Array II

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int left = 0, right = nums.size() - 1;
            while (left < right) {
                int mid = (left + right) / 2;
                if (nums[mid] > nums[right]) left = mid + 1;
                else if (nums[mid] < nums[right]) right = mid;
                else right--;
            }
            return nums[left];
        }
    };
    
    

    Problem 34. Search for a Range
    For this problem, you should deal with the right cases differently as you want your value always closer to right, so you need to ensure your right variable updating !!!

    
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int left = searchLeft(nums, target);
            int right = searchRight(nums, target);
            vector<int> result;
            result.push_back(left);
            result.push_back(right);
            return result;
        }
        
        int searchLeft(vector<int>& nums, int target) {
            int start = 0, end = nums.size() - 1;
            while (end > start) {
                int mid = start + (end - start) / 2;
                if (nums[mid] < target) start = mid + 1;
                else end = mid;
            }
            if (nums[start] == target)
                return start;
            else 
                return -1;
        }
        
        int searchRight(vector<int>& nums, int target) {
            int start = 0, end = nums.size() - 1;
            while (end > start) {
                int mid = start + (end - start) / 2 + 1;
                if (nums[mid] > target) end = mid - 1;
                else start = mid;
            }
            if (nums[start] == target)
                return start;
            else
                return -1;
        }
    };
    

    May the power with you !!!


Log in to reply
 

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